首页 > 代码库 > UVA - 11768 Lattice Point or Not (拓展gcd)

UVA - 11768 Lattice Point or Not (拓展gcd)

2024-07-19 06:57:59   223人阅读

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)


联系
我们