QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#224310 | #7511. Planar Graph | DAleksa | RE | 1ms | 3956kb | C++14 | 5.1kb | 2023-10-23 01:11:01 | 2023-10-23 01:11:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct Point {
int X, Y;
Point() { X = 0; Y = 0; }
Point(int x, int y) { X = x; Y = y; }
Point operator - (Point p) { return Point(X - p.X, Y - p.Y); }
};
int sign(long long n) { return (n > 0) - (n < 0); }
long long cross(Point a, Point b) { return a.X * b.Y - a.Y * b.X; }
long long cross(Point a, Point b, Point c) { return cross(b - a, c - a); }
int orientation(Point a, Point b, Point c) { return sign(cross(a, b, c)); }
bool segments_intersect(Point A, Point B, Point C, Point D) { return orientation(A, B, C) != orientation(A, B, D) && orientation(C, D, A) != orientation(C, D, B); }
bool in_triangle(Point P, Point A, Point B, Point C) {
if(orientation(P, A, B) == 0) return orientation(P, B, C) == orientation(P, C, A);
if(orientation(P, B, C) == 0) return orientation(P, C, A) == orientation(P, A, B);
if(orientation(P, C, A) == 0) return orientation(P, A, B) == orientation(P, B, C);
return orientation(P, A, B) == orientation(P, B, C) && orientation(P, B, C) == orientation(P, C, A);
}
struct edge {
int u;
int v;
};
const int N = 105;
int n, m, e;
Point a[N], b[N];
edge edges[3 * N];
bool connected[N][N], fake[N][N];
vector<int> faces[N][N];
int id = 0;
int face[N];
vector<int> g[N];
bool target[N];
bool mark[N];
bool dfs(int u) {
if(target[u]) return true;
if(mark[u]) return false;
mark[u] = true;
bool ans = false;
for(int v : g[u]) {
if(mark[v]) continue;
ans |= dfs(v);
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> e;
for(int i = 0; i < n; i++) cin >> a[i].X >> a[i].Y;
for(int i = 0; i < m; i++) cin >> b[i].X >> b[i].Y;
for(int i = 0; i < e; i++) {
cin >> edges[i].u >> edges[i].v;
edges[i].u--;
edges[i].v--;
connected[edges[i].u][edges[i].v] = connected[edges[i].v][edges[i].u] = true;
}
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(connected[i][j]) continue;
bool ok = true;
for(int i2 = 0; i2 < n; i2++) {
if(i2 == i || i2 == j) continue;
for(int j2 = i2 + 1; j2 < n; j2++) {
if(j2 == i || j2 == j) continue;
if(!connected[i2][j2]) continue;
if(segments_intersect(a[i], a[j], a[i2], a[j2])) {
ok = false;
break;
}
}
if(!ok) break;
}
if(ok) connected[i][j] = connected[j][i] = fake[i][j] = fake[j][i] = true;
}
}
for(int x = 0; x < n; x++) {
for(int y = x + 1; y < n; y++) {
for(int z = y + 1; z < n; z++) {
if(!connected[x][y] || !connected[y][z] || !connected[x][z]) continue;
bool ok = true;
for(int i = 0; i < n; i++) {
if(i == x || i == y || i == z) continue;
if(in_triangle(a[i], a[x], a[y], a[z])) {
ok = false;
break;
}
}
if(!ok) continue;
id++;
faces[x][y].push_back(id);
faces[x][z].push_back(id);
faces[y][z].push_back(id);
faces[y][x].push_back(id);
faces[z][x].push_back(id);
faces[z][y].push_back(id);
ok = false;
for(int i = 0; i < m; i++) {
if(in_triangle(b[i], a[x], a[y], a[z])) {
face[i] = id;
target[id] = true;
ok = true;
break;
}
}
if(!ok) target[0] = true;
}
}
}
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(faces[i][j].size() == 1) {
faces[i][j].push_back(0);
faces[j][i].push_back(0);
}
if(fake[i][j]) {
g[faces[i][j][0]].push_back(faces[i][j][1]);
g[faces[i][j][1]].push_back(faces[i][j][0]);
}
}
}
// for(int i = 0; i < n; i++) {
// for(int j = i + 1; j < n; j++) {
// if(connected[i][j]) {
// cout << i << " " << j << ": " << faces[i][j][0] << " " << faces[i][j][1] << "\n";
// }
// }
// }
for(int i = 0; i < e; i++) {
bool ok = false;
for(int j = 0; j < N; j++) mark[j] = false;
// cout << i << ": " << faces[edges[i].u][edges[i].v][0] << " " << faces[edges[i].u][edges[i].v][1] << "\n";
ok |= dfs(faces[edges[i].u][edges[i].v][0]);
for(int j = 0; j < N; j++) mark[j] = false;
ok |= dfs(faces[edges[i].u][edges[i].v][1]);
cout << ok;
}
return 0;
}
/*
4 1 3
-2 0
0 2
2 0
0 1
0 3
1 2
2 3
1 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3956kb
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: 3948kb
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
Runtime Error
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...