Ant Gathering

Problem Statement

二维平面上有 $n$ 只蚂蚁，每只蚂蚁有一条线段作为活动范围，第 $i$ 只蚂蚁的活动范围的两个端点为 $(u_i^ x,u_i^y), (v_i^x,v_i^y)$。现在蚂蚁们考虑在这些线段的交点处设置会议中心。为了尽可能节省经费，它们决定只在所有交点为整点的地方设置会议中心，请问需要设置多少个会议中心？

Input

输入共 $n + 1$ 行。

第一行为一个正整数 $n$。

后面 $n$ 行，每行 $4$ 个由空格分开的整数表示 $u_i^x, u_i^y,v_i^x,v_i^y$。

Output

输出共 $1$ 行，一个整数表示答案。

Sample Input

Sample Output

1

2

Constraints

对于 $20%$ 的评测用例，保证 $0 \le u_i^x, u_i^y, v_i^x, v_i^y\le 100$。
对于 $100%$ 的评测用例，保证 $n \le 500$，$0 \le u_i^x, u_i^y, v_i^x, v_i^y \le 10000$，保证任意蚂蚁的活动范围不会退化成一个点，不保证任意两条线段之间交点数量有限。

Solving

当两个端点位于同一横轴或纵轴时，通过对另一坐标按单位步长 1 增减，可以遍历线段上的所有整点。

当两个坐标不在同一个横轴或纵轴时，我们可以通过最大公约数确定横轴方向和纵轴方向上的步长，找到它们之间所有的整点。

我们假设线段的两个端点为$(x1,y1)$和$(x2,y2)$,我们分别求解出其横向和纵向方向向量：

$dx = x2 - x1$,

$dy = y2 - y1$

我们对两个方向向量分量的绝对值求取最大公因数:$d = gcd(|dy|,|dx|)$

其最小步长应为方向向量$(dx,dy)$对于d的:

$\Delta step_{x,y} = (dx/d,dy/d)$

求出横纵方向的最小步长后，只需从一端点一直枚举到另一线段端点，将其中经过的整数点对存入哈希表，遍历所有点对后，哈希表内出现次数大于等于2的点对数量即为答案.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


void solve()
{   
    int n;
    cin >> n;
    vector<tuple<int,int,int,int>> v(n);
    map<pair<int,int>,int> mp;
    auto check = [&](vector<tuple<int,int,int,int>>& v) -> void
    {
        for(auto [a,b,c,d] : v)
        {   
            // 求解方向向量
            int dx = c - a;
            int dy = d - b;
            // 得到方向向量模长的最大公因数
            int gcd = __gcd(abs(dx),abs(dy));
            dx /= gcd;
            dy /= gcd;
            // 约简后的向量 (dx/gcd, dy/gcd) 表示线段上相邻整点之间的最小位移
            for(int i=0;;i++)
            {
                int x = a + i * dx;
                int y = b + i * dy;
                mp[{x,y}]++;
                if(x==c&&y==d) break;
            }
        }
    };
    for(auto &[a,b,c,d] : v)
    {
        cin >> a >> b >> c >> d;
    }
    check(v);
    int ans = 0;
    for(auto x : mp)
    {
        if(x.second >= 2) ans++;
    }
    cout << ans << endl;
}