#CS1740. 交点

交点

题目背景

翻译自 CSES-1740 题。

题目描述

给定 n 条水平和垂直的线段，任务是计算它们的交点数量。

你可以假设没有平行的线段会交叉，且线段的端点不是交点。

输入格式

第一行包含一个整数 n，表示线段的数量。

接下来的 n 行每行包含四个整数：x1,y1,x2,y2x_1, y_1, x_2, y_2x1​,y1​,x2​,y2​，表示一条线段的起点为 (x1,y1)(x_1, y_1)(x1​,y1​)，终点为 (x2,y2)(x_2, y_2)(x2​,y2​)。

输出格式

输出一个整数：表示线段的交点数量。

样例

3
2 3 7 3
3 1 3 5
6 2 6 6

2

说明/提示

$1 \leq n \leq 10^5$

−106≤x1≤x2≤106-10^6 \leq x_1 \leq x_2 \leq 10^6−106≤x1​≤x2​≤106；

−106≤y1≤y2≤106-10^6 \leq y_1 \leq y_2 \leq 10^6−106≤y1​≤y2​≤106；

(x1,y1)≠(x2,y2)(x_1, y_1) \neq (x_2, y_2)(x1​,y1​)=(x2​,y2​)。