結果
問題 | No.849 yuki国の分割統治 |
ユーザー |
![]() |
提出日時 | 2019-07-05 23:05:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 201 ms / 2,000 ms |
コード長 | 1,922 bytes |
コンパイル時間 | 2,484 ms |
コンパイル使用メモリ | 204,228 KB |
最終ジャッジ日時 | 2025-01-07 06:07:27 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> #define rep(i, a, n) for(int i = a; i < n; i++) #define int long long using namespace std; typedef pair<int, int> P; typedef pair<P, P> PP; const int mod = 1000000007; const int INF = 1e18; int gcd(int a, int b){ if(a < b) swap(a, b); if(b == 0) return a; return gcd(b, a % b); } signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int a, b, c, d; cin >> a >> b >> c >> d; int n; cin >> n; if(a * d - b * c == 0){ if(a != 0){ set<P> st; rep(i, 0, n){ int x, y; cin >> x >> y; P v; v.first = a * y - b * x; v.second = a; int G = gcd(abs(v.first), abs(v.second)); v.first /= G; v.second /= G; st.insert(v); } cout << st.size() << endl; }else{ set<P> st; int G = gcd(b, d); rep(i, 0, n){ int x, y; cin >> x >> y; st.insert({x, (y % G + G) % G}); } cout << st.size() << endl; } return 0; } set<PP> st; rep(i, 0, n){ int x, y; cin >> x >> y; P u, v; u.second = v.second = a * d - b * c; u.first = d * x - c * y; v.first = a * y - b * x; if(u.second < 0){ u.first *= -1; u.second *= -1; v.first *= -1; v.second *= -1; } int G = gcd(abs(u.first), abs(u.second)); u.first /= G; u.second /= G; u.first = (u.first % u.second + u.second) % u.second; G = gcd(abs(v.first), abs(v.second)); v.first /= G; v.second /= G; v.first = (v.first % v.second + v.second) % v.second; st.insert({u, v}); } cout << st.size() << endl; }