結果
問題 | No.849 yuki国の分割統治 |
ユーザー |
|
提出日時 | 2023-12-09 19:49:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 68 ms / 2,000 ms |
コード長 | 1,392 bytes |
コンパイル時間 | 913 ms |
コンパイル使用メモリ | 84,752 KB |
最終ジャッジ日時 | 2025-02-18 09:50:36 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<set>#include<numeric>using namespace std;using ll=long long;#define all(v) v.begin(),v.end()#define rall(v) v.rbegin(),v.rend()template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;}template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);ll a,b,c,d;cin>>a>>b>>c>>d;int N;cin>>N;vector<ll>X(N),Y(N);for(int i=0;i<N;i++)cin>>X[i]>>Y[i];if(a*d==b*c){if(a!=0||c!=0){set<pair<ll,ll>>se;ll g=gcd(a,c);for(int i=0;i<N;i++){ll p=b*X[i]-a*Y[i],q=X[i]%g;se.insert(make_pair(p,q));}cout<<se.size()<<"\n";}else{set<pair<ll,ll>>se;ll g=gcd(b,d);for(int i=0;i<N;i++){ll p=b*X[i]-a*Y[i],q=Y[i]%g;se.insert(make_pair(p,q));}cout<<se.size()<<"\n";}}else{set<pair<ll,ll>>se;ll M=abs(a*d-b*c);for(int i=0;i<N;i++){ll p=(d*X[i]-c*Y[i])%M,q=(-b*X[i]+a*Y[i])%M;if(p<0)p+=M;if(q<0)q+=M;se.insert(make_pair(p,q));}cout<<se.size()<<"\n";}}