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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| #include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <set>
#include <tuple>
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef double db;
const int maxn = 1005;
const ldb eps = 1e-7;
int n, ans;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
struct Vector
{
ll x, y;
Vector(ll x_ = 0, ll y_ = 0):x(x_),y(y_){}
Vector(Vector a, Vector b)
{
x = b.x - a.x;
y = b.y - a.y;
}
bool operator < (const Vector &rhs) const
{
if(x == rhs.x) return y < rhs.y;
return x < rhs.x;
}
};
typedef Vector Point;
struct Line
{
ll a, b, c;
Line(Point p = Point(), Point v = Point())
{
Point V = Point(p, v);
a = -V.y;
b = V.x;
c = -p.x * a - p.y * b;
}
};
inline ll cnt_points
(tuple<Point, Point> tp)
{
Point x, y; tie(x, y) = tp;
return gcd(abs(x.x - y.x), abs(x.y - y.y)) + 1;
}
inline bool legal
(ll x1_, ll x2_, ll x)
{
if(x1_ > x2_) swap(x1_, x2_);
return x >= x1_ && x <= x2_;
}
inline bool on_seg
(tuple<Point, Point> tp, Point crs)
{
Point a, b; tie(a, b) = tp;
return legal(a.x, b.x, crs.x) && legal(a.y, b.y, crs.y);
}
inline bool intersect
(tuple<Point, Point> ta, tuple<Point, Point> tb, Point &c)
{
Point pa, va, pb, vb;
tie(pa, va) = ta; tie(pb, vb) = tb;
Line la(pa, va), lb(pb, vb);
ll a1(la.a), b1(la.b), c1(la.c);
ll a2(lb.a), b2(lb.b), c2(lb.c);
ll d1 = c1*b2 - b1*c2;
ll d2 = a1*c2 - c1*a2;
ll d3 = a1*b2 - b1*a2;
if(d3 == 0 || abs(d1) % abs(d3) || abs(d2) % abs(d3)) return false;
c = Point(-d1 / d3, -d2 / d3);
return on_seg(ta, c) && on_seg(tb, c);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n; vector<tuple<Point, Point> > v;
ll xl, yl, xr, yr;
for(int i = 1; i <= n; ++i)
{
cin >> xl >> yl >> xr >> yr;
v.push_back( make_tuple(Point(xl, yl), Point(xr, yr)) );
}
for(int i = 0; i < n; ++i)
{
ans += cnt_points(v[i]);
set<Point> all;
for(int j = i + 1; j < n; ++j)
{
Point crs;
if(intersect(v[i], v[j], crs))
all.insert(crs);
}
ans -= all.size();
}
cout << ans << endl;
return 0;
}
|
