結果

問題 No.849 yuki国の分割統治
ユーザー startcppstartcpp
提出日時 2019-07-06 13:02:26
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 185 ms / 2,000 ms
コード長 1,619 bytes
コンパイル時間 949 ms
コンパイル使用メモリ 88,496 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-04-16 08:31:05
合計ジャッジ時間 4,311 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 102 ms
6,016 KB
testcase_08 AC 102 ms
7,040 KB
testcase_09 AC 100 ms
6,272 KB
testcase_10 AC 102 ms
5,504 KB
testcase_11 AC 91 ms
6,144 KB
testcase_12 AC 96 ms
5,376 KB
testcase_13 AC 107 ms
6,656 KB
testcase_14 AC 103 ms
6,144 KB
testcase_15 AC 94 ms
6,912 KB
testcase_16 AC 130 ms
8,960 KB
testcase_17 AC 95 ms
5,376 KB
testcase_18 AC 131 ms
9,216 KB
testcase_19 AC 104 ms
5,760 KB
testcase_20 AC 119 ms
7,808 KB
testcase_21 AC 87 ms
5,376 KB
testcase_22 AC 185 ms
11,392 KB
testcase_23 AC 169 ms
10,496 KB
testcase_24 AC 114 ms
7,552 KB
testcase_25 AC 141 ms
10,112 KB
testcase_26 AC 1 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 1 ms
5,376 KB
testcase_29 AC 2 ms
5,376 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 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