将直线转化为ax + by = c的形式，然后扩展欧几里得求在[x1, x2]之间的解
对直线与坐标轴平行的特判
调试了好长时间，注意：
1 正负数转化为整型的处理
2 注意判断有无解
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
using namespace std;
typedef long long LL;
const int N = 1008, INF = 0x3F3F3F3F;
const double eps = 1e-6, meps = 1e-7;
LL Ext_gcd(LL a,LL b,LL &x,LL &y){//扩展欧几里得
if(b==0) { x=1, y=0; return a; }
LL ret= Ext_gcd(b,a%b,y,x);
y-= a/b*x;
return ret;
} LL gcd(LL a, LL b){
while(b){
LL t = a % b;
a = b;
b = t;
}
return a;
} LL cal(LL x1, LL x2, LL x, LL mod){
if(x1 > x2){
return 0;
}
if(x >= x1 && x <= x2){
return (x - x1) / mod + 1 + (x2 - x) / mod;
}
if(x < x1){
return (x2 - x) / mod - (x1 - 1 - x) / mod;
}
return (x - x1) / mod - (x - x2 - 1) / mod; }
LL toLL(double x){
if(x > 0){
return x + eps;
}
if(x < 0){
return x - eps;
}
return 0;
}
int main(){
double t1, t2, t3, t4;
int t;
scanf("%d", &t);
while(t--){
scanf("%lf %lf %lf %lf", &t1, &t2, &t3, &t4);
if(abs(t1 - t3) < eps){
if(abs(t1 - (LL)t1) < eps){
double t22 = min(t2, t4);
double t44 = max(t2, t4);
printf("%lld\n", cal((LL)ceil(t22), (LL)floor(t44), (LL)ceil(t22), 1));
}else{
printf("0\n");
}
continue;
} if(abs(t2 - t4) < eps){
if(abs(t2 - (LL)t2) < eps){
double t11 = min(t1, t3);
double t33 = max(t1, t3);
printf("%lld\n", cal((LL)ceil(t11), (LL)floor(t33), (LL)ceil(t11), 1));
}else{
printf("0\n");
}
continue;
} LL x1 = toLL(t1 * 10), y1 = toLL(t2 * 10), x2 = toLL(t3 * 10), y2 = toLL(t4 * 10); //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<"\n"; if(x1 > x2){
swap(x1, x2);
swap(y1, y2);
}
LL a = (y2 - y1) * 10, b = (x1 - x2) * 10;
LL c = x1 * y2 - x2 * y1;
LL gc = gcd(gcd(a, b), c);
a /= gc;
b /= gc;
c /= gc; //cout<<a<<" "<<b<<" "<<c<<" ***\n";
if(c % gcd(a, b)){
printf("0\n");
continue;
} //cout<<a * t1 + b * t2 - c<<" aa\n";
//cout<<a * t3 + b * t4 - c<<" aa\n";
LL x, y;
Ext_gcd(a, b, x, y);
//cout<<x<<" "<<y<<" xy\n";
x = c / gcd(a, b) * x;
//cout<<x<<" spe\n";
if(t1 > t3){
swap(t1, t3);
}
printf("%lld\n",cal((LL)ceil(t1), (LL)floor(t3), x, abs(b / gcd(a, b))));
//cout<<tp<<" cal\n";
} return 0;
}