QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#301477#7511. Planar GraphdefyersWA 2ms3988kbC++204.6kb2024-01-09 22:45:582024-01-09 22:45:59

Judging History

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

  • [2024-01-09 22:45:59]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3988kb
  • [2024-01-09 22:45:58]
  • 提交

answer

#include "bits/stdc++.h"
#include <algorithm>
#include <ostream>
#include <random>
using namespace std;

using ll = long long;
using LL = long long;
using pii = pair<int, int>;

using ull = unsigned long long;

template<class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	Point(T x = 0, T y = 0) : x(x), y(y) {}
	bool operator<(P p) { return tie(x, y) < tie(p.x, p.y); }
	bool operator==(P p) { return tie(x, y) == tie(p.x, p.y); }

	P operator+(P p) { return P(x+p.x, y+p.y); }
	P operator-(P p) { return P(x-p.x, y-p.y); }
	P operator*(T d) { return P(x*d, y*d); }
	P operator/(T d) { return P(x/d, y/d); }

	T dot(P p) { return x*p.x + y*p.y; }
	T cross(P p) { return x*p.y - y*p.x; }
	T cross(P a, P b) { return (a-*this).cross(b-*this); }
	T dist2() { return x*x + y*y; }
	double dist() { return sqrt(double(dist2())); }
	double angle() { return atan2(y, x); }

	P unit() { return *this / dist(); }
	P perp() { return P(-y, x); }
	P normal() { return perp().unit(); }

	friend ostream& operator<<(ostream& os, P p) {
		return os << "(" << p.x << "," << p.y << ")";
	}
};

using P = Point<double>;
double eps = 1e-9;

bool onSegment(P s, P e, P p) {
	return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
}

bool inPolygon(vector<P> &p, P a, bool strict = true) {
	int cnt = 0, n = int(size(p));
	for (int i = 0; i < n; i++) {
		P q = p[(i + 1) % n];
		if (onSegment(p[i], q, a)) return !strict;
		cnt ^= ((a.y < p[i].y) - (a.y < q.y)) * a.cross(p[i], q) > 0;
	}
	return cnt;
}

struct Edge {
	int id;
	int u, v;
	double angle;
	bool operator<(const Edge &o) const {
		if (fabs(angle - o.angle) > eps) return angle < o.angle;
		else return v < o.v;
	};
};

void solve(int TC) {
	int n, m, e;
	cin >> n >> m >> e;
	vector<P> baseP(n), sourceP(m);

	for (int i = 0; i < n; i++) {
		ll x, y;
		cin >> x >> y;
		baseP[i] = {double(x), double(y)};
	}
	for (int i = 0; i < m; i++) {
		ll x, y;
		cin >> x >> y;
		sourceP[i] = {double(x), double(y)};
	}

	vector<vector<Edge>> g(n);
	vector<Edge> edge;
	for (int i = 0; i < e; i++) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		edge.push_back({ 2 * i, u, v, (baseP[v] - baseP[u]).angle() });
		g[u].push_back(edge.back());
		edge.push_back({ 2 * i + 1, v, u, (baseP[u] - baseP[v]).angle() });
		g[v].push_back(edge.back());
	}

	for (int i = 0; i < n; i++) {
		sort(g[i].begin(), g[i].end());
	}

	vector<int> nextedge(2 * e);
	for (int i = 0; i < 2 * e; i++) {
		int v = edge[i].v;
		auto iter = lower_bound(g[v].begin(), g[v].end(), edge[i ^ 1]);
		if (iter == g[v].begin()) iter = g[v].end();
		--iter;
		nextedge[i] = (*iter).id;
	}

	int face = 0;
	vector<vector<P>> facePoly; 
	vector<int> belong(2 * e, -1);
	for (int i = 0; i < 2 * e; i++) {
		if (belong[i] != -1) continue;
		belong[i] = belong[nextedge[i]] = face;
		double area = 0;
		facePoly.push_back({baseP[edge[i].u], baseP[edge[i].v]});
		for (int j = nextedge[i]; edge[j].v != edge[i].u; j = nextedge[j], belong[j] = face) {
			facePoly[face].push_back(baseP[edge[j].v]);
			area += baseP[edge[i].u].cross(baseP[edge[j].u], baseP[edge[j].v]);
		}
		
		if (face <= eps) { // 0 or negative -> non-close polygon
			facePoly[face] = {};
		}

		face++;
	}

	// for (int i = 0; i < 2 * e; i++) {
	// 	cout << i << " : " << belong[i] << endl;
	// }

	vector<P> intervalP(2 * e);
	for (int i = 0; i < e; i++) {
		auto [id, u, v, _] = edge[2 * i];
		intervalP[2 * i] = (baseP[u] + baseP[v]) / 2 + (baseP[v] - baseP[u]).normal() * 10 * eps;
		intervalP[2 * i + 1] = (baseP[u] + baseP[v]) / 2 - (baseP[v] - baseP[u]).normal() * 10 * eps;
	}


	mt19937_64 rng(42);
	vector<ull> sourcePHash(m), intervalPHash(2 * e);
	for (int i = 0; i < face; i++) {
		// cout << "i: " << i << " --- ";
		// for (auto x: facePoly[i]) {
		// 	cout << x << " ";
		// }
		// cout << "\n";

		if (facePoly[i].empty()) continue;
		ull hash = rng();
		for (int j = 0; j < m; j++) {
			if (inPolygon(facePoly[i], sourceP[j])) {
				sourcePHash[j] ^= hash;
			}
		}
		for (int j = 0; j < 2 * e; j++) {
			if (inPolygon(facePoly[i], intervalP[j])) {
				intervalPHash[j] ^= hash;
			}
		}
	}

	unordered_set<ull> S;
	S.reserve(m * 2);
	for (int i = 0; i < m; i++) S.insert(sourcePHash[i]);

	for (int i = 0; i < e; i++) {
		if (S.count(intervalPHash[2 * i]) || S.count(intervalPHash[2 * i + 1])) {
			cout << "1";
		}
		else {
			cout << "0";
		}
	}
	cout << "\n";
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	int t = 1;
	// cin >> t;

	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3808kb

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: 1ms
memory: 3936kb

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: 0
Accepted
time: 1ms
memory: 3988kb

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:

011111111111111111100001011000001001110111110111101011011001111110011011101111110111011101001000000001010100111111100110000100110100101101111111110011001111111100100011

result:

ok single line: '011111111111111111100001011000...1111111110011001111111100100011'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3900kb

input:

59 1 158
-51 8
50 48
-56 -67
19 7
33 -47
32 44
42 47
-36 -57
15 34
-8 23
-24 43
20 11
61 -41
58 -11
-68 -45
36 -54
-21 42
-28 -49
-28 -31
-34 20
29 -65
-13 38
-22 -36
-30 11
-40 57
64 -69
65 51
47 34
-41 31
-1 35
28 -11
58 58
13 12
-52 43
40 6
46 48
46 -59
-52 30
69 -23
-34 38
-1 -5
-12 -27
-11 24
-...

output:

00000000000000000000000000000000000000000000000000000000000001000000000000000000000000000001000000000000000000000000000000000000000000000000001000000000000000

result:

ok single line: '000000000000000000000000000000...0000000000000001000000000000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3828kb

input:

92 1 125
55 10
67 -85
-26 80
36 -32
44 -64
41 -50
-93 -80
-66 -92
-68 27
-79 9
87 -61
-40 -64
89 100
75 -42
59 40
60 -30
-66 27
63 90
-19 100
24 -20
-13 83
-100 -92
-83 58
-33 -70
74 -20
-55 73
-41 28
27 -31
-37 -22
40 18
-3 -2
70 79
71 29
32 -73
39 -1
17 -95
-61 56
94 -10
-79 -66
-84 87
-16 71
52 4...

output:

10010010000101001010010100101100100000001010001000000001101111101000011111000000001011000100000010100000000100011011000000110

result:

ok single line: '100100100001010010100101001011...0010100000000100011011000000110'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3916kb

input:

85 47 204
48 93
-32 10
71 70
-37 10
20 -12
-32 -56
1 -22
-46 -64
56 82
-19 63
-5 83
16 89
79 81
51 -22
43 59
33 -87
28 67
-18 38
-16 -23
18 -78
87 66
-83 29
36 58
6 -2
68 80
18 -34
-17 59
-31 -12
-37 -75
33 -79
-51 -24
-88 6
-19 62
71 -78
-51 72
-49 -45
21 41
-58 33
46 67
-11 -31
62 46
54 55
37 -14
...

output:

000110010001001101100010110101100100011110011110110101010100110011111010101110101001001011100000110101000100010011100100100110100001011010001010001010000100011000001101010110011001101111010000011001000011

result:

ok single line: '000110010001001101100010110101...0011001101111010000011001000011'

Test #7:

score: -100
Wrong Answer
time: 1ms
memory: 3892kb

input:

59 96 152
-75886847 147807525
335545968 317138952
262969730 -308175740
91308409 -162085508
-397786268 -191693417
-227565597 195627938
45666011 253210394
-311142459 58197832
-412164189 -270215767
-12639523 -314154358
-269901472 -366179516
-306681757 -167771007
194329800 -339296479
-12501616 -15788817...

output:

00000001000000001100000010001010100010010000100010000000110110000010001001000000000001000000101000000101000111010010100000000000011000000011110001010001

result:

wrong answer 1st lines differ - expected: '011101111111111111101011101110...1110001111100010111110111111111', found: '000000010000000011000000100010...0000000011000000011110001010001'