链接: https://cses.fi/problemset/task/1740

板块: Geometry

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定 $n$ 条水平与竖直的线段，你的任务是计算它们交点的数量。

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

输入

第一行包含一个整数 $n$：线段的数量。

接下来有 $n$ 行描述这些线段。每行包含四个整数 $x_1$、$y_1$、$x_2$ 和 $y_2$：一条线段从点 $(x_1,y_1)$ 开始，到点 $(x_2,y_2)$ 结束。

输出

输出交点的数量。

数据范围

$1 \le n \le 10^5$ $-10^6 \le x_1 \le x_2 \le 10^6$ $-10^6 \le y_1 \le y_2 \le 10^6$ $(x_1,y_1) \neq (x_2,y_2)$

样例输入

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

样例输出

2