← 返回题目列表

Codeforces · 1036/E

E. 覆盖点

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

笛卡尔平面上有 $$$n$$$ 段。每个线段的端点都有整数坐标。线段可以彼此相交。没有两个线段位于同一条线上。

计算至少被一段覆盖的具有整数坐标的不同点的数量。

输入

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

接下来的 $$$n$$$ 行包含四个整数 $$$Ax_i, Ay_i, Bx_i, By_i$$$ ($$$-10^6 \le Ax_i, Ay_i, Bx_i, By_i \le 10^6$$$) — 端点的坐标 $$$A$$$, $$$B$$$第 $$$i$$$ 段的 ($$$A \ne B$$$)。

保证没有两个线段位于同一条线上。

输出

打印单个整数 - 具有整数坐标的不同点的数量,这些点至少被一个线段覆盖。

示例

输入 #1

9
0 0 4 4
-1 5 4 0
4 0 4 4
5 2 11 2
6 1 6 7
5 6 11 6
10 1 10 7
7 0 9 8
10 -1 11 -1

输出 #1

42

输入 #2

4
-1 2 1 2
-1 0 1 0
-1 0 0 3
0 3 1 0

输出 #2

7

注意

第一个示例的图像:

几个关键点被标记为蓝色,答案也包含一些未标记的点。

第二个示例的图像: