QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#301477 | #7511. Planar Graph | defyers | WA | 2ms | 3988kb | C++20 | 4.6kb | 2024-01-09 22:45:58 | 2024-01-09 22:45:59 |
Judging History
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'