首页 > 代码库 > UVA - 11768 Lattice Point or Not (拓展gcd)
UVA - 11768 Lattice Point or Not (拓展gcd)
Input
First line of the input file contains a positive integer N(N<=50000) that denotes how many lines of inputs follow. This line isfollowed by N lines each of which contains four floating-point numbers x1, y1,x2, y2 (0< |x1|, |y1|, |x2|, |y2|<=200000). These floating-point numbers has exactly one digit after thedecimal point.
Output
For each line of input exceptthe first line produce one line of output. This line contains an integer whichdenotes how many lattice points are there on the line segment that connects thetwo points (x1, y1) and (x2, y2).
SampleInput Output for Sample Input
3 10.1 10.1 11.2 11.2 10.2 100.3 300.3 11.1 1.0 1.0 2.0 2.0 | 1 0 2
|
Problemsetter: Shahriar Manzoor
Special Thanks: Derek Kisman
题意:求一条线段经过的整数点个数
思路:先将线段转换成直线方程,那么我们就可以用拓展gcd来求解了,然后就是找这两个点范围内的解就是了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> typedef long long ll; using namespace std; 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 sovle(double X1, double Y1, double X2, double Y2) { ll x1 = X1*10, x2 = X2*10, y1 = Y1*10, y2 = Y2*10; if (x1 == x2) { if (x1 % 10) return 0; y1 = ceil(min(Y1, Y2)); y2 = floor(max(Y1, Y2)); return max(y2-y1+1, 0ll); } if (y1 == y2) { if (y1 % 10) return 0; if (X2 < X1) swap(X2, X1); x1 = ceil(X1), x2 = floor(X2); return max(x2-x1+1, 0ll); } ll a = (y2-y1)*10, b = (x1-x2)*10, c = x1*y2-x2*y1; ll x, y, d, k1 = 0; if (X2 < X1) swap(X2, X1); x1 = ceil(X1), x2 = floor(X2); if (x1 > x2) return 0; gcd(a, b, d, x, y); if (c % d != 0) return 0; a /= d, b /= d; x *= (c/d), y *= (c/d); if (b < 0) b = -b; x = x-(x-x1)/b*b; x -= b; while (x < x1) x += b; k1 = 0; while (x + k1 * b <= x2) k1++; return k1; } int main() { double x1, y1, x2, y2; int t; scanf("%d", &t); while (t--) { scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); ll ans = sovle(x1, y1, x2, y2); printf("%lld\n", ans); } return 0; }
UVA - 11768 Lattice Point or Not (拓展gcd)