結果

問題 No.849 yuki国の分割統治
ユーザー startcpp
提出日時 2019-07-06 13:02:26
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 147 ms / 2,000 ms
コード長 1,619 bytes
コンパイル時間 756 ms
コンパイル使用メモリ 89,340 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-10-06 23:50:56
合計ジャッジ時間 3,956 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int a, b, c, d;
int n;
int x[100000], y[100000];

//y > 0, x : int
int modulo(int x, int y) {
	if (x >= 0) return x % y;
	return (y - (-x) % y) % y;
}

int solve2() {
	int i;
	int det = abs(a * d - b * c);
	typedef pair<int, int> P;
	set<P> dict;
	
	rep(i, n) {
		int det_mul_s = d * x[i] - c * y[i];
		int det_mul_t = -b * x[i] + a * y[i];
		int modS = modulo(det_mul_s, det);
		int modT = modulo(det_mul_t, det);
		dict.insert(P(modS, modT));
	}
	return dict.size();
}

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int solve1(vector<int> vs, int a, int b, int x[]) {
	int i;
	set<int> dict;
	
	rep(i, vs.size()) {
		int xx = x[vs[i]];
		int modG = xx % gcd(a, b);
		dict.insert(modG);
	}
	return dict.size();
}

signed main() {
	int i;
	
	cin >> a >> b >> c >> d;
	cin >> n;
	rep(i, n) cin >> x[i] >> y[i];
	
	if (a * d - b * c != 0) {
		cout << solve2() << endl;
	}
	else {
		map<int, vector<int>> mp;
		map<int, vector<int>>::iterator it;
		rep(i, n) {
			//(x, y)と(x', y')が同じ直線上 ⇔ a * y - b * x == a * y' - b * x'
			mp[a * y[i] - b * x[i]].push_back(i);
		}
		
		//同じ直線上にある点集合について1次元の問題を解く
		int ans = 0;
		for (it = mp.begin(); it != mp.end(); it++) {
			vector<int> vs = it->second;
			int res;
			if (a != 0) {
				res = solve1(vs, a, c, x);
			}
			else {
				res = solve1(vs, b, d, y);
			}
			ans += res;
		}
		cout << ans << endl;
	}
	return 0;
}
0