QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225067 | #7511. Planar Graph | DAleksa | RE | 8ms | 6640kb | C++14 | 5.1kb | 2023-10-23 22:19:13 | 2023-10-23 22:19:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
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 * 1LL * b.Y - a.Y * 1LL * 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) {
set<int> s;
s.insert(orientation(P, A, B));
s.insert(orientation(P, B, C));
s.insert(orientation(P, C, A));
if(s.find(0) != s.end()) s.erase(0);
return s.size() == 1;
}
struct edge {
int u;
int v;
};
const int N = 105, M = 100005;
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[M];
bool target[M];
bool mark[M];
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;
}
signed 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);
for(int i = 0; i < m; i++) {
if(in_triangle(b[i], a[x], a[y], a[z])) {
face[i] = id;
target[id] = true;
}
}
}
}
}
for(int i = 0; i < m; i++) {
if(face[i] == 0) {
target[0] = true;
break;
}
}
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 < M; 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 < M; 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
6 3 6
-5 0
5 0
0 5
-1 1
1 1
0 2
-3 0
-2 2
-10 10
1 2
1 3
2 3
4 5
4 6
5 6
6 1 6
-6 0
6 0
0 6
-1 1
1 1
0 2
-3 3
1 2
1 3
2 3
4 5
4 6
5 6
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6368kb
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: 6372kb
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: 4ms
memory: 6556kb
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: 3ms
memory: 6320kb
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: 8ms
memory: 6352kb
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: 6ms
memory: 6628kb
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: 0
Accepted
time: 3ms
memory: 6424kb
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:
01110111111111111110101110111011101111110011100110100111110110001110111101100111100111010111111110110101110111110011111001110001111100010111110111111111
result:
ok single line: '011101111111111111101011101110...1110001111100010111110111111111'
Test #8:
score: 0
Accepted
time: 0ms
memory: 6432kb
input:
62 1 99 -72 -45 -58 -44 -39 5 -45 -56 11 -26 -7 56 -29 -56 -70 -26 64 -64 -12 6 4 44 -14 68 -28 29 -68 -52 -21 -10 19 -37 17 -30 26 64 -40 2 -11 -30 64 -45 38 -67 43 -35 67 -49 50 72 -60 -2 -28 37 55 55 -7 42 -63 -32 71 35 -55 26 -67 -49 -42 -43 69 59 -29 5 0 -36 -1 8 -53 66 1 -6 -2 32 -51 -61 -27 6...
output:
000010000000000110001101000110000000010010000001001001100000010010000010001100010011010101001000010
result:
ok single line: '000010000000000110001101000110...0010001100010011010101001000010'
Test #9:
score: 0
Accepted
time: 3ms
memory: 6320kb
input:
63 1 175 50549954 -224104196 -187903718 57327090 -61398050 89271831 72686467 -167765054 4226095 73332567 -80682032 -158732552 -366425325 -180661648 -210787891 -107411752 44235201 233049038 -29484914 -280845598 228925315 -106736012 -169221325 64453690 -127160591 78410226 374001485 -312357450 31528300...
output:
0000000100000000000000000000000000010000000000000000000001000000000000000010000000000000000000000000000000000010000000000000010000000000000001000000000100000101000000000001000
result:
ok single line: '000000010000000000000000000000...0000000100000101000000000001000'
Test #10:
score: 0
Accepted
time: 5ms
memory: 6332kb
input:
82 4 66 182782804 77923360 117828203 139218692 -110620000 89777361 273011388 138341008 294610527 -194481138 294204618 -290402347 194417551 48839146 -161919200 -261350494 -260772975 -239789170 117370125 245536520 -201599590 -82451402 291486591 84106590 296266013 309943147 -220542664 54399074 24021444...
output:
111101011111111111111111010111111101010111100110100011111111011111
result:
ok single line: '111101011111111111111111010111...1010111100110100011111111011111'
Test #11:
score: 0
Accepted
time: 4ms
memory: 6400kb
input:
65 50 147 -581452360 190355182 -642896619 -572084384 -305018177 -539060586 -328404608 -74526018 198824769 -402666976 -604806291 420433161 646918331 -591294299 360443372 -456307852 253325248 -341024549 -656241212 302363402 524405246 -499973260 -531933602 617077471 -185233072 -318131117 -362315669 -49...
output:
011111111110100110100010010101111011110111010001101101001001111101111111011011011001001001101100100111110111001101101010100100110111100110101010100
result:
ok single line: '011111111110100110100010010101...1010100100110111100110101010100'
Test #12:
score: 0
Accepted
time: 3ms
memory: 6640kb
input:
71 1 142 26 16 -81 21 53 -64 -46 67 -37 73 46 79 66 -27 46 53 38 -44 16 44 -44 -43 -8 -30 65 12 60 2 -26 -24 7 71 -31 -27 -13 0 -80 80 77 -65 71 2 8 -53 -64 -71 52 -58 30 53 61 -18 56 -34 -80 -13 80 56 -28 -79 -43 -52 -38 77 11 -1 -30 -73 -39 30 -61 69 -41 66 16 -45 40 -51 37 40 -26 34 57 29 -15 -8 ...
output:
1000000100000100000000001001000000000010101000000100000011001000000000000001000000000000000000000000000000000000000010011000000000000000000010
result:
ok single line: '100000010000010000000000100100...0000010011000000000000000000010'
Test #13:
score: 0
Accepted
time: 6ms
memory: 6296kb
input:
88 68 244 452074073 749836590 -422267242 -370342423 -649645359 303851355 285738514 -585228292 674035872 344344527 -564943027 45741258 301794983 564572022 349063999 218051130 668851769 598897930 596201080 -750109936 95583385 363387733 130300372 -350613210 -126422550 -684185703 -117024972 -406661982 -...
output:
1111011101010010110011001011101101100000000010100110001111000010001011100110001100101100000010001011101100010000010110111000010101010100101011011101011010011110000111010000011110110111101110011111001111101000110001000110101101001101111100111101
result:
ok single line: '111101110101001011001100101110...1000110101101001101111100111101'
Test #14:
score: 0
Accepted
time: 1ms
memory: 6368kb
input:
24 47 58 -536382548 -36211682 -617682678 630246425 -680303961 -753887401 -576626558 -547501154 -166237320 -247093489 -780629487 -564369462 745821462 -462233962 -29960131 -120134355 -215230222 568441689 -505349805 471834374 -268168811 -773902784 -436226654 -153342090 -686102938 -414449668 -318346027 ...
output:
1011111110101111101111111011101111100110100110101011111011
result:
ok single line: '1011111110101111101111111011101111100110100110101011111011'
Test #15:
score: 0
Accepted
time: 6ms
memory: 6288kb
input:
76 82 181 -835091273 636197461 -809826661 -915012307 -514114180 762992620 -801978217 -646901746 -937647819 -73101245 632623370 -798225996 -949969476 -45929520 677089833 -491546441 -818746494 -457407341 -23609804 -63980274 927682282 -371416961 -936340868 -741789992 -82906350 -740214368 -884276937 -32...
output:
1011111111110100011011111001011110100011001111111001011100111111111110011100101011101011101011111011001100001001110001101110010010101111000101010100111100011011110001100110110110011
result:
ok single line: '101111111111010001101111100101...1100011011110001100110110110011'
Test #16:
score: 0
Accepted
time: 6ms
memory: 6348kb
input:
95 1 39 1 -2 5 -59 6 23 77 57 87 -81 96 -9 20 45 -41 5 -80 -76 62 -83 -26 93 89 -61 -104 -65 55 4 50 55 61 -39 -26 -18 -90 -98 -14 38 56 -61 -100 105 92 -4 30 -98 -13 -27 -21 27 -49 95 62 20 91 24 -75 -30 68 -4 -86 84 -17 -13 -93 13 -38 -64 40 -82 63 47 -9 28 -95 7 91 -51 -50 -66 54 27 -3 -12 -8 -89...
output:
110111101111111110111011111111111111111
result:
ok single line: '110111101111111110111011111111111111111'
Test #17:
score: 0
Accepted
time: 2ms
memory: 6388kb
input:
53 1 95 249310291 444009281 -51319591 -127058272 -521364452 184610945 -21697253 -380031119 -765296404 788815734 480089046 -792178676 285516793 131912022 715950950 -65482217 36211136 -559456984 -46323546 622669323 812068024 -71601366 -6695845 -158750172 23940379 638024824 -792521738 -179875992 -72088...
output:
00000000000010000100000000000100000000000000000000000000000000000000000100000000000000000000000
result:
ok single line: '000000000000100001000000000001...0000000100000000000000000000000'
Test #18:
score: 0
Accepted
time: 8ms
memory: 6336kb
input:
90 87 67 -37 -98 66 -40 17 24 -32 51 -68 56 -47 78 -83 66 -16 -22 41 -12 -31 86 -1 11 42 65 -27 2 -19 -21 -54 78 -14 -77 -74 5 -46 82 -19 63 76 43 -39 -7 62 -49 68 4 -26 72 -91 0 -40 -74 9 -68 92 64 21 88 53 -55 32 -12 100 -26 9 -24 43 -93 -99 19 -76 -3 21 97 -57 -92 -28 26 -10 -95 96 -11 43 -82 22 ...
output:
1111111111111111111111111111110111111111111111111111111111111111111
result:
ok single line: '111111111111111111111111111111...1111111111111111111111111111111'
Test #19:
score: 0
Accepted
time: 2ms
memory: 6264kb
input:
27 42 12 -196639452 -910071469 556979079 -24132720 -907504137 -798429714 217201737 894945050 592735402 -891961813 351726786 -961077191 428253659 -337157490 -814353097 482187973 -746163779 14512669 -639377173 -925754520 -499592664 319782459 -500528351 591167527 -701230268 -495398846 -836405665 445706...
output:
111111111111
result:
ok single line: '111111111111'
Test #20:
score: 0
Accepted
time: 3ms
memory: 6496kb
input:
63 28 102 -65 69 73 -1 0 -30 -69 -66 48 39 3 -37 52 26 13 18 19 -61 -9 54 24 30 -62 58 -64 -64 -6 -3 48 -24 -58 -59 -45 -1 19 -44 64 13 69 -31 38 13 73 -50 -7 -43 4 58 38 56 -21 36 -36 40 -73 17 23 63 -18 63 41 14 47 68 -16 -47 -30 61 -33 43 -45 25 -31 22 -42 2 1 -40 -17 -2 -65 6 21 -58 31 -15 3 -50...
output:
011111100111111110111110011111010010001111111101100111011111111011110101110101011001111111011111111010
result:
ok single line: '011111100111111110111110011111...1110101011001111111011111111010'
Test #21:
score: 0
Accepted
time: 5ms
memory: 6372kb
input:
81 70 214 501181684 467604004 467393962 79858372 -24971604 -76855555 310835183 -451578432 529058882 -371153027 10117013 439009502 -102203223 498873755 104983339 -167287519 -234656041 548196249 -355162848 -403411047 -303715296 -31203991 412378489 -143945211 -38540379 -474967805 -321224760 115499601 -...
output:
0010100000110011101001110011111111000011110110011000110000111111000110011111000001000100111000101111110111101011101110100000001101010100110100011011111111000100110110010100010001101111000101110110010110011010110000
result:
ok single line: '001010000011001110100111001111...1000101110110010110011010110000'
Test #22:
score: -100
Runtime Error
input:
2 1 0 -381381789 -155480688 476986136 269997025 374524257 360034879