結果
問題 | No.849 yuki国の分割統治 |
ユーザー | jupiro |
提出日時 | 2020-01-21 18:58:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 68 ms / 2,000 ms |
コード長 | 2,097 bytes |
コンパイル時間 | 1,082 ms |
コンパイル使用メモリ | 121,472 KB |
実行使用メモリ | 8,576 KB |
最終ジャッジ日時 | 2024-07-06 00:05:55 |
合計ジャッジ時間 | 3,561 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <cstdio> #include <iostream> #include <string> #include <sstream> #include <stack> #include <algorithm> #include <cmath> #include <queue> #include <map> #include <set> #include <cstdlib> #include <bitset> #include <tuple> #include <assert.h> #include <deque> #include <bitset> #include <iomanip> #include <limits> #include <chrono> #include <random> #include <array> #include <unordered_map> #include <functional> #include <complex> template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const long long MAX = 5100000; const long long INF = 1LL << 60; const long long mod = 1000000007LL; //const long long mod = 998244353LL; using namespace std; typedef unsigned long long ull; typedef long long ll; ll gcd(ll x, ll y) { ll r; if (x < y) { swap(x, y); } while (y > 0) { r = x % y; x = y; y = r; } return x; } long long extGCD(long long a, long long b, long long& x, long long& y) { if (b == 0) { x = 1; y = 0; return a; } long long d = extGCD(b, a % b, y, x); y -= a / b * x; return d; } int main() { /* cin.tie(nullptr); ios::sync_with_stdio(false); */ ll a, b, c, d; cin >> a >> b >> c >> d; ll adbc = llabs(a * d - b * c); ll n; scanf("%lld", &n); ll res = 0; set<pair<ll, ll>> s; if (adbc == 0) { vector<ll> x(n), y(n); for (ll i = 0; i < n; i++) scanf("%lld %lld", &x[i], &y[i]); if (gcd(a, c) == 0) { swap(a, b); swap(c, d); for (ll i = 0; i < n; i++) swap(x[i], y[i]); } ll e, f; a = extGCD(a, c, e, f); b = b * e + d * f; for (ll i = 0; i < n; i++) { auto p = make_pair(x[i] % a, y[i] - x[i] / a * b); s.insert(p); } } else { for (ll i = 0; i < n; i++) { ll x, y; scanf("%lld %lld", &x, &y); ll r1 = d * x - c * y; ll r2 = -b * x + a * y; r1 %= adbc; r2 %= adbc; if (r1 < 0) r1 += adbc; if (r2 < 0) r2 += adbc; auto p = make_pair(r1, r2); //cout <<i<< " "<< r1 << " " << r2 << endl; s.insert(p); } } cout << s.size() << endl; return 0; }