Lattice Point or Not UVA - 11768（拓展欧几里得）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
using namespace std;

typedef long long LL;
double X1,Y1,X2,Y2;

void gcd(LL a,LL b,LL& d,LL& x,LL& y)
{
    if(!b)  {d=a;x=1;y=0;}
    else { gcd(b,a%b,d,y,x); y-=x*(a/b);}
}

LL solve()
{
    LL x1=X1*10, y1=Y1*10, x2=X2*10, y2=Y2*10;
    if(x1==x2)                    //平行y轴
    {
        if(x1%10)  return 0;      //原来的X1为小数,肯定不是整点
        if(Y2<Y1)  swap(Y1,Y2);
        return floor(Y2)-ceil(Y1)+1;
    }
    if(y1==y2)
    {
        if(y1%10)  return 0;
        if(X2<X1)  swap(X1,X2);
        return  floor(X2)-ceil(X1)+1;
    }
    LL a=(y2-y1)*10, b=(x1-x2)*10, c=y2*x1-y1*x2;  //c相当于扩大了100倍，所以前面还得乘10
    LL d,x,y;
    gcd(a,b,d,x,y);
    if(c%d)   return 0;      //扩展欧几里得算法无解的判断

    x=x*c/d; y=y*c/d;        //获得一组整数解(x,y)
    b=abs(b/d);             //这里的b其实就是b‘

    if(X1>X2)   swap(X1,X2);
    x1=ceil(X1);
    x2=floor(X2);
    if(x1>x2) return 0;

    x=x+(x1-x)/b*b;        //使x进入[x1,x2]的区间内
    if(x<x1)  x+=b;
    if(x>x2)  return 0;
    return (x2-x)/b+1;
}

int main()
{
    //freopen("D:\\input.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
        LL ans = solve();
        printf("%lld\n",ans);
    }
    return 0;
}