11069번: Particle

https://www.acmicpc.net/problem/11069

d = gcd(a, b)
(a', b') = (a / d, b / d)

주어진 직사각형을 각 변에 대한 거울상과 무한히 연결하고 이 필드 상에서 입자가 직선 운동을 한다고 생각할 수 있다.
문제의 규칙 하에 입자가 (x0, y0)에서 (x1, y1)로 속도(a', b')로 간다면 걸리는 최소 시간 tm은 다음 식을 만족하는 t(>0)중 최솟값이다.

i) x0 + a't = x1 + 2w*u  and  y0 + b't = y1 + 2h*v
ii) x0 + a't = -x1 + 2w*u  and  y0 + b't = y1 + 2h*v
iii) x0 + a't = x1 + 2w*u  and  y0 + b't = -y1 + 2h*v
iv) x0 + a't = -x1 + 2w*u and  y0 + b't = -y1 + 2h*v

이 중 (i)에 대해서만 풀어보자.
두 식은 모두 Extended Euclidean 알고리즘으로 일반해를 구할 수 있다.
첫 번째 식의 t = p1 * x + q1,
두 번째 식의 t = p2 * y + q2 라 하자.
두 t는 같아야 하므로 p1 * x + q1 = p2 * y + q2
이를 만족하는 x 역시 Extended Euclidean 알고리즘으로 일반해를 구할 수 있다.
x = p3 * x' + q3라 하면
t = p1 * x + q1 = p1*p3*x' + q1*p3 + q3
이제 위 식을 만족하면서 0보다 큰 최소 t를 구할 수 있다.

마찬가지 방법으로 (i)~(iv)에 대해 구한 t 중 최솟값 tm을 구할 수 있다.
(x2, y2)에 가는데 걸리는 최소 시간 또한 같은 방법으로 구해서 걸린 시간을 비교한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int t, w, h, a0, b0, a1, b1, a2, b2, a, b;
int ee(int c1, int c2, int &r1, int &r2) {
    if (!c2) {
        r1 = 1; r2 = 0;
        return c1;
    }
    int ret = ee(c2, c1%c2, r2, r1);
    r2 -= c1 / c2*r1;
    return ret;
}
bool eq(int c1, int c2, int c3, int &r1, int &r2) {
    int u, v, ret = ee(c1, c2, u, v);
    if (c3%ret) return false;
    r1 = c2 / ret;
    r2 = 1LL * c3 / ret * u%r1;
    return true;
}
long long solve(int c1, int c2) {
    int p1, q1, p2, q2, p3, q3;
    if (!eq(a, -2 * w, c1 - a0, p1, q1) ||
        !eq(b, -2 * h, c2 - b0, p2, q2) ||
        !eq(p1, -p2, q2 - q1, p3, q3)) return 1e15;
    long long p4 = abs(1LL * p1*p3), q4 = 1LL * p1*q3 + q1;
    return (q4%p4 + p4) % p4;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d%d%d%d%d%d%d%d%d", &w, &h, &a0, &b0, &a1, &b1, &a2, &b2, &a, &b);
        int u, v, d = abs(ee(a, b, u, v));
        a /= d; b /= d;
        long long ret1 = min({ solve(a1, b1), solve(-a1, b1), solve(a1, -b1), solve(-a1, -b1) }),
            ret2 = min({ solve(a2, b2), solve(-a2, b2), solve(a2, -b2), solve(-a2, -b2) });
        puts(ret1^ret2 ? ret1 < ret2 ? "A" : "B" : "O");
    }
    return 0;
}