笛卡尔平面上有 $$$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
注意
第一个示例的图像:
几个关键点被标记为蓝色,答案也包含一些未标记的点。
第二个示例的图像: