제출 #1118781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118781		YSH2020	Portal (BOI24_portal)	C++17	11 / 100	88 ms	3732 KiB

Main

//lmao not bezout lemma bash
/*
suppose there is a portal on (x1, y1), (x2, y2), and (x3, y3)
then C(x, y) = C(x+k(x2-x1), y+k(y2-y1)),
and C(x, y) = C(x+k(x3-x1), y+k(y3-y1))
C(0, 0) = C(a(x2-x1), a(y2-y1)) = C(a(x2-x1)+b(x3-x1), a(y2-y1)+b(y3-y1)). Note removal of constant terms.
thus, we try to maintain a constant x while seeing how the y will change, resulting in a vertical period.
same for horizontal period.
now we just multiply them tgt. to form a conclusion!

example: (0, 0), (4, 6), (1, 3) as below
C(4a+1b, 6a+3b)
(0, 0) -> 0
(-1, 4) -> 6
etc. shows difference in y-coords
0 <- (0, 0)
-2 <- (-1, 2)

example: (
-1000000 -99999
-1000000 1000000
1000000 -1000000
)
(0a+2000000b, 1099999a+900001b)
of course, if we have a bunch of periods, (like period of 2 period of 3 etc. just take gcd of them all)
very mathematical approach!
so now we translate into code!

an obvious claim: if there are less than 3, you can colour infinitely.
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a, int b) {
    if (a < 0) a *= -1;
    if (b < 0) b *= -1;
    if (b > a) swap(a, b);
    if (b == 0) return a;
    return gcd(b, a%b);
}

pair<int, int> get_period(int change_x1, int change_x2, int change_y1, int change_y2) {
    if (change_x1 == 0 or change_x2 == 0 or change_y1 == 0 or change_y2 == 0) {
        int period_x = 0;
        int period_y = 0;
        if (change_x1 == 0) {period_y = gcd(period_y, change_y1); period_x = gcd(period_x, change_x2);}
        if (change_x2 == 0) {period_y = gcd(period_y, change_y2); period_x = gcd(period_x, change_x1);}
        if (change_y1 == 0) {period_x = gcd(period_x, change_x1); period_y = gcd(period_y, change_y2);}
        if (change_y2 == 0) {period_x = gcd(period_x, change_x2); period_y = gcd(period_y, change_y1);}
        return {period_x, period_y};
    }

    int tmp = gcd(change_x1, change_x2);
    int period_y;
    if (tmp == 0) period_y = 0;
    else {
        int a = -change_x2/tmp;
        int b = change_x1/tmp;
        period_y = change_y1*a+change_y2*b;
    }
    tmp = gcd(change_y1, change_y2);
    int period_x;
    if (tmp == 0) period_x = 0;
    else {
        int a = -change_y2/tmp;
        int b = change_y1/tmp;
        period_x = change_x1*a+change_x2*b;
    }
    return {abs(period_x), abs(period_y)};
}

signed main() {
    int n; cin >> n;
    if (n < 3) {cout << -1; return 0;}
    int start_x1, start_y1; cin >> start_x1 >> start_y1;
    int start_x2, start_y2; cin >> start_x2 >> start_y2;
    vector<pair<int, int>> periods;
    for (int i = 0; i < n-2; i++) {
        int x, y; cin >> x >> y;
        periods.push_back(get_period((start_x2-start_x1), (x-start_x1), 
        (start_y2-start_y1), (y-start_y1)));
    }
    int ans_x = 0;
    int ans_y = 0;
    for (int i = 0; i < n-2; i++) {
        //note one fun property of the gcd code: you can gcd 0 with any integer to get that integer.
        ans_x = gcd(ans_x, periods[i].first);
        ans_y = gcd(ans_y, periods[i].second);
    }
    if (ans_x == 0 or ans_y == 0) cout << -1;
    else {
        long long ans = ans_x*ans_y;
        cout << ans;
    }
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 29
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35