結果

問題 No.849 yuki国の分割統治
コンテスト
ユーザー 梧桐
提出日時 2026-05-20 02:51:22
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 73 ms / 2,000 ms
コード長 1,286 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,165 ms
コンパイル使用メモリ 94,676 KB
実行使用メモリ 9,728 KB
最終ジャッジ日時 2026-05-20 02:51:33
合計ジャッジ時間 8,909 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstdio>
#include <set>
#include <cmath>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PLL;

const int N = 100010;

struct Point {
    int x, y;
};

int n, a, b, c, d;
LL mod;
Point p[N];
set<PLL> s;

int GCD(int x, int y) {
    return y ? GCD(y, x % y) : x;
}

int main() {
    scanf("%d%d%d%d%d", &a, &b, &c, &d, &n);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &p[i].x, &p[i].y);

    mod = abs(1LL * a * d - 1LL * b * c);
    if (mod == 0LL) {
        int gx = GCD(a, c), gy = GCD(b, d);
        for (int i = 1; i <= n; ++i) {
            if (gx == 0) {
                s.insert({ p[i].x, p[i].y % gy });
            } else if (gy == 0) {
                s.insert({ p[i].x % gx, p[i].y });
            } else {
                int k = min(p[i].x / gx, p[i].y / gy);
                s.insert({ p[i].x - k * gx , p[i].y - k * gy });
            }
        }
    } else {
        for (int i = 1; i <= n; ++i) {
            PLL v;
            v.first = (1LL * d * p[i].x - 1LL * c * p[i].y) % mod;
            (v.first += mod) %= mod;
            v.second = (1LL * b * p[i].x - 1LL * a * p[i].y) % mod;
            (v.second += mod) %= mod;
            s.insert(v);
        }
    }
    printf("%d\n", (int) s.size());

    return 0;
}
0