本文主要是介绍UVA - 11768 Lattice Point or Not (拓展gcd)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Now a days a very common problem is:“The coordinate of two points in Cartesian coordinate system is (200, 300) and(4000, 5000). If these two points are connected we get a line segment. How manylattice points are there on this line segment.” You will have to do a similartask in this problem – the only difference is that the terminal coordinates canbe fractions.
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)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
