UVA11768 Lattice Point or Not

21 May 2019 | duanyll | Tags: OI 题解 数论 exgcd

洛谷水黑题，不过考试的时候把我坑惨了，推了一个半小时都没有推出来，太弱了。。。

题意

在二维坐标系中给定两个点$A(x_1, y_1)$和$B(x_2, y_2)$，$x_1$, $x_2$, $y_1$, $y_2$均为$0.1$的整数倍，求线段$AB$经过多少个格点。

分析

给出的是两点坐标求直线，应该用直线的两点式方程入手。

\[\frac{y-y_1}{x-x_1}=\frac{y-y_2}{x-x_2}\]

交叉相乘整理得一般式

\[(y_2-y_1)x + (x_1-x_2)y = y_2x_1 - y_1x_2\]

求这样的式子的整数解，显然需要exgcd。但是题目给出的是小数，还好只有一位，坐标都扩大十倍。

\[(10y_2-10y_1)\cdot \color{red}{10}x + (10x_1-10x_2)\cdot\color{red}{10}y = 100y_2x_1 - 100y_1x_2\]

写代码时不要忘了乘上红色的系数！

然后exgcd常规操作，求出直线上的一个整点$(x_0,y_0)$

\[x_0 = x*\frac{c}{gcd(a,b)},y_0=y*\frac{c}{gcd(a,b)}\]

并且其它整点满足

\[x = x_0 + \frac{b}{gcd(a,b)} * t,y = y_0 - \frac{a}{gcd(a,b)} * t\]

这样求出来的点保证在直线上，我们就不用考虑y坐标，只用管x坐标了。

x坐标上整点出现的周期是$abs(b/gcd(a,b))$，将$x_0$移动到目标区间开头：

int64 xbegin = x + (l - x) / xrep * xrep;

答案就是

(r - xbegin) / xrep + 1

代码

注意特判两点式不成立的情况：平行于坐标轴。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <fstream>
#include <cctype>
using namespace std;

typedef long long int64;
const int64 INF = 0x3f3f3f3f3f3f3f3fll;

int64 exgcd(int64 a, int64 b, int64 &x, int64 &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    int64 GCD = exgcd(b, a % b, x, y);
    int64 tmp = x;
    x = y;
    y = tmp - a / b * y;
    return GCD;
}

inline double dbread() {
    double X = 0, Y = 1.0;
    int w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) X = X * 10 + (ch ^ 48), ch = getchar();
    ch = getchar(); 
    while (isdigit(ch)) X += (Y /= 10) * (ch ^ 48), ch = getchar();
    return w ? -X : X;
}

int main() {
	int tcnt;
	cin >> tcnt;
	for (int T = 1; T <= tcnt; T++) {
		double x1 = dbread();
		double y1 = dbread();
		double x2 = dbread();
		double y2 = dbread();
		
		int64 X1 = x1 * 10, X2 = x2 * 10, Y1 = y1 * 10, Y2 = y2 * 10;
		if (x1 == x2) {
			if (X1 % 10 != 0) {
				cout << 0 << endl;
			} else {
				if (y2 < y1) {
					swap(y1, y2);
				}
				cout << floor(y2) - ceil(y1) + 1 << endl;
			}
		} else if (y1 == y2) {
			if (Y1 % 10 != 0) {
				cout << 0 << endl;
			} else {
				if (x2 < x1) {
					swap(x2, x1);
				}
				cout << floor(x2) - ceil(x1) + 1 << endl;
			}
		} else {
			int64 A = (Y2 - Y1) * 10, B = (X1 - X2) * 10;
			int64 C = Y2 * X1 - Y1 * X2;
			int64 x, y;
			int64 GCD = exgcd(A, B, x, y);
			if (C % GCD != 0) {
				cout << 0 << endl;
			} else {
				x = x * C / GCD;
				int64 xrep = abs(B / GCD);
				if (x1 > x2) {
					swap(x1, x2);
				}
				int64 l = ceil(x1);
				int64 r = floor(x2);
				if (l <= r) {
					int64 xbegin = x + (l - x) / xrep * xrep;
					if (xbegin < l) {
						xbegin += xrep;
					} 
					if (xbegin > r) {
						cout << 0 << endl;
					} else {
						cout << (r - xbegin) / xrep + 1 << endl;
					}
				} else {
					cout << 0 << endl;
				}
			}
		}
	}
}