QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#190346#7511. Planar Graphucup-team1209WA 3ms16160kbC++203.3kb2023-09-28 18:42:172023-09-28 18:42:17

Judging History

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

  • [2023-09-28 18:42:17]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:16160kb
  • [2023-09-28 18:42:17]
  • 提交

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 vis[N];
int contain(std::vector<vec2> a, vec2 o) { bool in = 0;
	for(int i = 0;i < (int) a.size();++i) {
		vec2 x = a[i] - o, y = a[(i + 1) % a.size()] - o;
		if(!x.x && !x.y) return 0;
		if(x.y > y.y) std::swap(x, y);
		if(x.y <= 0 && y.y > 0 && x * y < 0) in ^= 1;
	}
	return in;
}

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 ^ 1, edge[(i + 1) % edge.size()].second);
		}
	}
	std::vector<int> out;
	std::vector<std::pair<std::vector<vec2>, int>> A, B;
	for(int i = 2;i <= e * 2 + 1;++i) if(!vis[i]) {
		int j = go[i];
		vis[i] = 1;
		std::vector<vec2> ss = {start[i]};
		for(;j != i;j = go[j]) {
			vis[j] = 1;
			ss.push_back(start[j]);
		}
		reverse(ss.begin(), ss.end());
		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) {
			B.emplace_back(ss, i);
		} else {
			A.emplace_back(ss, i);
		}
	}
	auto area = [&](const std::vector<vec2> & ss) {
		ll sum = 0;
		for(int i = 2;i < (int) ss.size();++i) {
			sum += (ss[i - 1] - ss[0]) * (ss[i] - ss[0]);
		}
		return sum < 0 ? -sum : sum;
	};
	sort(A.begin(), A.end(), [&](auto x, auto y) {
		return area(x.first) < area(y.first);
	});
	for(auto [b, bid] : B) {
		int id = -1;
		for(auto [ss, ID] : A) {
			int ok = 1;
			for(auto x : b) {
				ok = ok && contain(ss, x);
			}
			if(ok) {
				id = ID;
				break;
			}
		}
		if(id > 0) {
			un(bid, id);
		} else {
			out.push_back(bid);
		}
	}
	for(int i = 1;i < (int) out.size();++i) {
		un(out[i - 1], out[i]);
	}
	for(int i = 1;i <= m;++i) {
		int seted = 0;
		for(auto [ss, ID] : A) {
			if(contain(ss, b[i])) {
				ok[find(ID)] = 1;
				seted = 1;
				break;
			}
		}
		if(!seted) {
			for(int x : out) ok[find(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: 15900kb

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: 3ms
memory: 16160kb

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: 0ms
memory: 15860kb

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:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

result:

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