QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#189328#7511. Planar Graphucup-team1209#WA 2ms13772kbC++202.8kb2023-09-27 11:46:192023-09-27 11:46:20

Judging History

你现在查看的是最新测评结果

  • [2023-09-27 11:46:20]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:13772kb
  • [2023-09-27 11:46:19]
  • 提交

answer

#include<bits/stdc++.h>
using ll = long long;
using std::cin;
using std::cout;
const int N = 200005;

struct vec2 { ll x, y; } a[N], b[N];
ll operator * (vec2 x, vec2 y) { return x.x * y.y - x.y * y.x; }
vec2 operator + (vec2 x, vec2 y) { return {x.x + y.x, x.y + y.y}; }
vec2 operator - (vec2 x, vec2 y) { return {x.x - y.x, x.y - y.y}; }
int half(vec2 x) { return x.y < 0 || (x.y == 0 && x.x <= 0); }
int cmp(vec2 a, vec2 b) { return half(a) == half(b) ? a * b > 0 : half(b); }

int n, m, e;
using pr = std::pair<int, int>;
std::vector<pr> edge[N];
int anc[N];
int ok[N];
vec2 start[N];
int find(int x) {
	return anc[x] == x ? x : anc[x] = find(anc[x]);
}
int go[N];
void un(int x, int y) {
	go[x] = y;
	anc[find(x)] = find(y);
}
std::vector<pr> v;

int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m >> e;
	for(int i = 1;i <= n;++i) {
		cin >> a[i].x >> a[i].y;
	}
	for(int i = 1;i <= m;++i) {
		cin >> b[i].x >> b[i].y;
	}
	for(int i = 1;i <= e * 2 + 1;++i) anc[i] = i;
	for(int i = 1, x, y;i <= e;++i) {
		cin >> x >> y;
		edge[x].emplace_back(y, i * 2 + 0);
		edge[y].emplace_back(x, i * 2 + 1);
		start[i * 2] = a[x];
		start[i * 2 + 1] = a[y];
		v.emplace_back(x, y);
	}
	for(int i = 1;i <= n;++i) {
		sort(edge[i].begin(), edge[i].end(), [&](pr x, pr y) {
			vec2 u = a[x.first] - a[i];
			vec2 v = a[y.first] - a[i];
			return cmp(u, v);
		});
		auto edge = ::edge[i];
		for(int i = 0;i < (int) edge.size();++i) {
			un(edge[i].second, edge[(i + 1) % edge.size()].second ^ 1);
		}
	}
	std::vector<int> out;
	for(int i = 2;i <= e * 2 + 1;++i) {
		int j = go[i];
		std::vector<vec2> ss = {start[i]};
		for(;j != i;j = go[j]) {
			ss.push_back({start[j]});
		}
		ll sum = 0;
		for(int i = 2;i < (int) ss.size();++i) {
			sum += (ss[i - 1] - ss[0]) * (ss[i] - ss[0]);
		}
		if(sum >= 0) {
			out.push_back(find(i));
		}
	}
	for(int i = 1;i < (int) out.size();++i) un(out[i - 1], out[i]);
	for(int i = 1;i <= m;++i) {
		int id = -1;
		ll A = 1e18, B = 1;
		for(int j = 0;j < e;++j) {
			auto [x, y] = v[j];
			auto u = a[x];
			auto v = a[y];
			if(u.y > b[i].y && v.y > b[i].y) {
				continue;
			}
			if(u.y < b[i].y && v.y < b[i].y) {
				continue;
			}
			ll C = (u.y - b[i].y) * v.x + (b[i].y - v.y) * u.x;
			ll D = (u.y - v.y);
			if(!D) continue;
			if(D < 0) C *= -1, D *= -1;
			using i128 = __int128;
			if((i128) C < (i128) b[i].x * D) {
				continue;
			}
			if((i128) A * D > (i128) C * B) {
				A = C;
				B = D;
				id = j * 2 + 2;
				if(u.y > v.y) {
					id += 1;
				}
			}
		}
		if(id > 0) ok[find(id)] = 1;
		else {
			for(int x : out) ok[x] = 1;
		}
	}
	for(int i = 1;i <= e;++i) {
		if(ok[find(i * 2)] || ok[find(i * 2 + 1)]) {
			cout.put(1 + 48);
		} else {
			cout.put(0 + 48);
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 13724kb

input:

4 1 3
-2 0
0 2
2 0
0 1
0 3
1 2
2 3
1 3

output:

111

result:

ok single line: '111'

Test #2:

score: 0
Accepted
time: 0ms
memory: 13772kb

input:

13 35 13
13 12
16 -3
18 4
4 -7
23 -22
9 -23
23 11
12 -1
19 -5
15 -15
5 -15
-17 11
-17 -13
-20 19
11 -12
-10 14
-3 14
7 -4
-10 -23
-19 -12
-13 1
-22 10
-21 -1
18 -9
-8 1
13 22
12 -23
-9 -9
-12 -20
4 -3
-6 17
14 -10
10 13
-5 -2
-4 -12
13 22
-18 -21
19 5
12 -18
4 0
3 -17
5 -2
-2 0
8 0
-8 1
14 -18
3 -9
...

output:

1111111111111

result:

ok single line: '1111111111111'

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 13716kb

input:

68 59 168
51 -57
-26 -51
-31 58
-45 -78
-46 -49
-53 14
76 -69
-64 32
58 -49
-1 12
-65 28
-15 -10
29 -53
25 -32
78 -41
24 -37
69 56
54 -10
3 36
-18 46
53 -30
41 -2
-30 13
-58 -37
-20 42
-48 -38
-42 22
64 0
9 -56
7 -11
-66 -23
19 -9
-26 -6
-61 -68
57 13
-13 50
-15 -11
-77 47
-77 57
78 51
-37 56
-75 24...

output:

011111111111111111100001011000001001110111110111101011011001111110011011101111110111011101100000000001010100110111100110000100110100101101111111110011001111111100100011

result:

wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '011111111111111111100001011000...1111111110011001111111100100011'