QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#301514 | #7511. Planar Graph | defyers | WA | 2ms | 3852kb | C++20 | 5.7kb | 2024-01-10 00:38:07 | 2024-01-10 00:38:07 |
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;
using int128 = __int128;
ostream& operator<<(ostream& os, int128 p) {
if (p == 0) return os << 0;
string s;
bool flag = 0;
if (p < 0) { flag = 1; p *= -1; }
while (p) { s += '0' + p % 10; p /= 10; }
if (flag) s += '-';
reverse(s.begin(), s.end());
return os << s;
}
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(ll(y), ll(x)); }
P unit() { return *this / dist(); }
P perp() { return P(-y, x); }
P normal() { return perp().unit(); }
int phase() {
if (y != 0) return y > 0 ? 0 : 1;
return x > 0 ? 0 : 1;
}
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")";
}
};
using P = Point<int128>;
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));
int128 A = 0;
for (int i = 0; i < n - 1; i++) {
P q = p[(i + 1) % n];
A += p[i].cross(q);
}
if (A == 0) return true;
if (A < 0) {
cnt = 1;
}
for (int i = 0; i < n - 1; 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;
bool operator==(const Edge &o) {
return id == o.id;
}
};
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;
x *= 2, y *= 2;
baseP[i] = {x, y};
}
for (int i = 0; i < m; i++) {
ll x, y;
cin >> x >> y;
x *= 2, y *= 2;
sourceP[i] = {x, 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 });
g[u].push_back(edge.back());
edge.push_back({ 2 * i + 1, v, u });
g[v].push_back(edge.back());
}
for (int i = 0; i < n; i++) {
sort(g[i].begin(), g[i].end(), [&](Edge& a, Edge& b) {
P u = baseP[a.v] - baseP[i], v = baseP[b.v] - baseP[i];
if (u.phase() != v.phase()) return u.phase() < v.phase();
return u.cross(v) > 0;
});
// for (auto [id, u, v]: g[i]) {
// cout << "!!!" << id << " " << u << " " << v << endl;
// }
}
vector<int> nextedge(2 * e);
for (int i = 0; i < 2 * e; i++) {
int v = edge[i].v;
auto iter = find(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] = face;
facePoly.push_back({baseP[edge[i].u], baseP[edge[i].v]});
for (int j = nextedge[i]; belong[j] == -1; j = nextedge[j]) {
belong[j] = i;
facePoly[face].push_back(baseP[edge[j].v]);
}
face++;
}
// for (int i = 0; i < 2 * e; i++) {
// cout << i << " : " << belong[i] << endl;
// }
vector<P> intervalP(e);
for (int i = 0; i < e; i++) {
auto [id, u, v] = edge[2 * i];
intervalP[i] = (baseP[u] + baseP[v]) / 2;
}
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;
// cout << "face: " << i << endl;
ull hash = rng();
for (int j = 0; j < m; j++) {
if (inPolygon(facePoly[i], sourceP[j])) {
// cout << "source point: " << j << " poly: " << i << endl;
sourcePHash[j] ^= hash;
}
}
for (int j = 0; j < e; j++) {
bool online = false;
if (belong[2 * j] == i) {
online = true;
// cout << "interval mp: " << 2 * j << " poly: " << i << endl;
intervalPHash[2 * j] ^= hash;
}
if (belong[2 * j + 1] == i) {
online = true;
// cout << "interval mp: " << 2 * j + 1 << " poly: " << i << endl;
intervalPHash[2 * j + 1] ^= hash;
}
if (!online && inPolygon(facePoly[i], intervalP[j])) {
// cout << "interval mp: " << 2 * j << " " << 2 * j + 1 << " poly: " << i << endl;
intervalPHash[2 * j] ^= hash;
intervalPHash[2 * j + 1] ^= hash;
}
}
}
// for (int i = 0; i < e; i++) {
// cout << intervalPHash[2 * i] << " " << intervalPHash[2 * i + 1] << endl;
// }
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: 0ms
memory: 3852kb
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: 3532kb
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: 3708kb
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:
011111111110111111100001011000101001101111010011001011101001011110110011101011111111110100000011000011010101100100100011001100000100101101011000111011100100001001101001
result:
wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '011111111110111111100001011000...1011000111011100100001001101001'