結果
問題 | No.849 yuki国の分割統治 |
ユーザー |
![]() |
提出日時 | 2019-07-05 21:50:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 63 ms / 2,000 ms |
コード長 | 1,213 bytes |
コンパイル時間 | 996 ms |
コンパイル使用メモリ | 91,744 KB |
実行使用メモリ | 10,240 KB |
最終ジャッジ日時 | 2024-10-06 21:27:25 |
合計ジャッジ時間 | 3,186 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <set> #include <cmath> #include <tuple> #include <vector> #include <cassert> #include <iostream> using namespace std; long long gcd(long long x, long long y) { if (y == 0) return x; return gcd(y, x % y); } int main() { cin.tie(0); ios_base::sync_with_stdio(false); long long A, B, C, D; int N; cin >> A >> B >> C >> D >> N; vector<long long> X(N), Y(N); for (int i = 0; i < N; ++i) { cin >> X[i] >> Y[i]; } if (B * C - A * D != 0) { set<pair<long long, long long> > d; for (int i = 0; i < N; ++i) { long long xc = B * X[i] - A * Y[i]; long long yc = D * X[i] - C * Y[i]; bool xt = false, yt = false; if (xc < 0) xt = true, xc *= -1; xc %= abs(B * C - A * D); if (xt && xc != 0) xc = abs(B * C - A * D) - xc; if (yc < 0) yt = true, yc *= -1; yc %= abs(D * A - C * B); if (yt && yc != 0) yc = abs(D * A - C * B) - yc; d.insert(make_pair(xc, yc)); } cout << d.size() << endl; } else { long long gx = gcd(A, C), gy = gcd(B, D); long long g = gcd(gx, gy); set<tuple<long long, long long, long long> > d; for (int i = 0; i < N; ++i) { d.insert(make_tuple(gy * X[i] - gx * Y[i], X[i] % g, Y[i] % g)); } cout << d.size() << endl; } return 0; }