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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <fstream>
#include <cctype>
using namespace std;
typedef long long int64;
const int64 INF = 0x3f3f3f3f3f3f3f3fll;
int64 exgcd(int64 a, int64 b, int64 &x, int64 &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int64 GCD = exgcd(b, a % b, x, y);
int64 tmp = x;
x = y;
y = tmp - a / b * y;
return GCD;
}
inline double dbread() {
double X = 0, Y = 1.0;
int w = 0;
char ch = 0;
while (!isdigit(ch)) {
w |= ch == '-';
ch = getchar();
}
while (isdigit(ch)) X = X * 10 + (ch ^ 48), ch = getchar();
ch = getchar();
while (isdigit(ch)) X += (Y /= 10) * (ch ^ 48), ch = getchar();
return w ? -X : X;
}
int main() {
int tcnt;
cin >> tcnt;
for (int T = 1; T <= tcnt; T++) {
double x1 = dbread();
double y1 = dbread();
double x2 = dbread();
double y2 = dbread();
int64 X1 = x1 * 10, X2 = x2 * 10, Y1 = y1 * 10, Y2 = y2 * 10;
if (x1 == x2) {
if (X1 % 10 != 0) {
cout << 0 << endl;
} else {
if (y2 < y1) {
swap(y1, y2);
}
cout << floor(y2) - ceil(y1) + 1 << endl;
}
} else if (y1 == y2) {
if (Y1 % 10 != 0) {
cout << 0 << endl;
} else {
if (x2 < x1) {
swap(x2, x1);
}
cout << floor(x2) - ceil(x1) + 1 << endl;
}
} else {
int64 A = (Y2 - Y1) * 10, B = (X1 - X2) * 10;
int64 C = Y2 * X1 - Y1 * X2;
int64 x, y;
int64 GCD = exgcd(A, B, x, y);
if (C % GCD != 0) {
cout << 0 << endl;
} else {
x = x * C / GCD;
int64 xrep = abs(B / GCD);
if (x1 > x2) {
swap(x1, x2);
}
int64 l = ceil(x1);
int64 r = floor(x2);
if (l <= r) {
int64 xbegin = x + (l - x) / xrep * xrep;
if (xbegin < l) {
xbegin += xrep;
}
if (xbegin > r) {
cout << 0 << endl;
} else {
cout << (r - xbegin) / xrep + 1 << endl;
}
} else {
cout << 0 << endl;
}
}
}
}
}
|
