UVa 11768 Lattice Point or Not_综合

题目

https://vjudge.net/problem/UVA-11768

题解

上一次做到这里感觉很烦躁写不出来跳到数据结构去了，然后隔了两天重新回来做，做了一下午加半个晚上，vjudge提交记录一版都是我的qwq。

首先思路一定要清晰，这题变量多得不得了，调试非常困难，经常调到一半，诶我要求啥来着？这是啥意思？这个等于啥？

思路：先找到这条线段上的一个整点（没有就特判），然后计算出每隔多长会出现一个整点，利用这两个信息找出线段上最接近x较小的那个点的整点，然后计算一下这里到x较大那个点会出现多少整点。

大体框架是这样，然后一步一步实现。

先找整点，这题很讨厌的就是坐标是0.1的整数倍（还好不是0.01的整数倍），所以考虑把坐标全部扩大10倍，因为根据两点式推出直线方程是 $(y_2-y_1)x+(x_1-x_2)y=x_2y_1-y_1x_2$ ，设 $a=y_2-y_1,b=x_1-x_2,c=x_2y_1-y_1x_2$ ，那么此时a和b为0.1的倍数，c为0.01的倍数，我们现在没有办法直接找出一组解来，因为并不是整数。所以两边同乘100，这样就能找出一组解。

还可以表示出通解，x的通解可表示为 $x=x_0+k*b',b'=b/gcd(a,b)$ 其实这个b’就是每隔多长会出现一个整点了。然后照上面说的算一下就好了。

另外注意特判两个点横坐标或者纵坐标相等的情况，这种情况很好算的。注意算的时候c可能会爆int，要开longlong。

qwq理解起来有一定难度。

代码

//QWsin
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;void exgcd(long long  a,long long  b,long long  &g,long long  &x,long long  &y)
{if(!b){g=a;x=1;y=0;return ;}exgcd(b,a%b,g,y,x);y-=a/b*x;
}inline long long  solve()
{double X1,Y1,X2,Y2;cin>>X1>>Y1>>X2>>Y2;long long  x1=X1*10,y1=Y1*10,x2=X2*10,y2=Y2*10;if(x1==x2){if(x1%10) return 0;if(Y1>Y2) swap(Y1,Y2);return max((long long )(floor(Y2)-ceil(Y1)+1),0ll);}if(y1==y2){if(y1%10) return 0;if(X1>X2) swap(X1,X2);return max((long long )(floor(X2)-ceil(X1)+1),0ll);}long long  a=(y2-y1)*10,b=(x1-x2)*10,g,x,y,c=y2*x1-x2*y1;exgcd(a,b,g,x,y);if(c%g!=0) return 0;a/=g;b/=g;x*=c/g;y*=c/g;if(b<0) b=-b;if(X1>X2) swap(X1,X2);x1=ceil(X1),x2=floor(X2);if(x1>x2) return 0;x=x-(x-x1)/b*b;if(x<x1) x+=b;if(x>x2) return 0;return (x2-x)/b+1;
}int  main()
{long long  T;cin>>T;while(T--) printf("%lld\n",solve());return 0;
}