← 返回题目列表

Codeforces · 1194/E

E. 计算矩形

中文机器翻译题面 查看原题

平面上绘制了 $$$n$$$ 个线段;第 $$$i$$$ 段连接两个点 ($$$x_{i, 1}$$$, $$$y_{i, 1}$$$) 和 ($$$x_{i, 2}$$$, $$$y_{i, 2}$$$)。每个段都是非退化的,并且要么是水平的,要么是垂直的——正式来说,对于每个 $$$i \in [1, n]$$$ 要么 $$$x_{i, 1} = x_{i, 2}$$$ 要么 $$$y_{i, 1} = y_{i, 2}$$$ (但只有其中一个条件成立)。只有不同类型的线段可以相交:没有一对水平线段共享任何公共点,也没有一对垂直线段共享任何公共点。

如果满足以下条件,我们说具有索引 $$$h_1$$$、$$$h_2$$$、$$$v_1$$$ 和 $$$v_2$$$ 的四个线段使得 $$$h_1 < h_2$$$ 和 $$$v_1 < v_2$$$ 形成一个矩形:

- 段 $$$h_1$$$ 和 $$$h_2$$$ 是水平的;
- 段 $$$v_1$$$ 和 $$$v_2$$$ 是垂直的;
- 线段 $$$h_1$$$ 与线段 $$$v_1$$$ 相交;
- 线段 $$$h_2$$$ 与线段 $$$v_1$$$ 相交;
- 线段 $$$h_1$$$ 与线段 $$$v_2$$$ 相交;
- 线段 $$$h_2$$$ 与线段 $$$v_2$$$ 相交。

请计算选择四个线段使它们形成一个矩形的方法数。请注意,条件 $$$h_1 < h_2$$$ 和 $$$v_1 < v_2$$$ 应成立。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$) — 段数。

然后是 $$$n$$$ 行。第 $$$i$$$ 行包含四个整数 $$$x_{i, 1}$$$、$$$y_{i, 1}$$$、$$$x_{i, 2}$$$ 和 $$$y_{i, 2}$$$ 表示第 $$$i$$$ 段的端点。端点的所有坐标均在 $$$[-5000, 5000]$$$ 范围内。

保证每个段都是非退化的并且是水平或垂直的。此外,如果两个线段共享一个公共点,则其中一个线段是水平的,另一个线段是垂直的。

输出

打印一个整数 — 选择四个线段以形成矩形的方法数。

示例

输入 #1

7
-1 4 -1 -2
6 -1 -2 -1
-2 3 6 3
2 -2 2 4
4 -1 4 3
5 3 5 1
5 2 1 2

输出 #1

7

输入 #2

5
1 5 1 0
0 1 5 1
5 4 0 4
4 2 4 0
4 3 4 5

输出 #2

0

注意

下图为示例案例: