結果

問題 No.849 yuki国の分割統治
ユーザー startcppstartcpp
提出日時 2019-07-06 13:01:13
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,604 bytes
コンパイル時間 742 ms
コンパイル使用メモリ 88,628 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2024-10-06 23:50:41
合計ジャッジ時間 3,854 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 1 ms
6,820 KB
testcase_07 WA -
testcase_08 AC 89 ms
6,912 KB
testcase_09 AC 89 ms
6,816 KB
testcase_10 AC 92 ms
6,816 KB
testcase_11 AC 83 ms
6,816 KB
testcase_12 AC 93 ms
6,820 KB
testcase_13 AC 97 ms
6,816 KB
testcase_14 AC 93 ms
6,820 KB
testcase_15 AC 83 ms
6,816 KB
testcase_16 AC 105 ms
8,832 KB
testcase_17 AC 87 ms
6,816 KB
testcase_18 AC 114 ms
9,088 KB
testcase_19 AC 93 ms
6,816 KB
testcase_20 AC 103 ms
7,680 KB
testcase_21 AC 79 ms
6,816 KB
testcase_22 AC 154 ms
11,264 KB
testcase_23 AC 145 ms
10,496 KB
testcase_24 AC 106 ms
7,424 KB
testcase_25 AC 123 ms
10,240 KB
testcase_26 AC 1 ms
6,820 KB
testcase_27 AC 1 ms
6,816 KB
testcase_28 AC 1 ms
6,816 KB
testcase_29 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

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 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);
			}
			else {
				res = solve1(vs, b, d);
			}
			ans += res;
		}
		cout << ans << endl;
	}
	return 0;
}
0