QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#294184 | #7511. Planar Graph | OAleksa | WA | 2ms | 4412kb | C++14 | 3.6kb | 2023-12-30 09:30:23 | 2023-12-30 09:30:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 310;
const int M = 1e4 + 69; //ko ce racunati ovo?
struct point {
int x, y;
} a[N], b[N];
int n, m, e, c[M], ans[N], z[M];
vector<int> g[M], f[M];
vector<int> t[M];
int edge[N][N];
int cross(point a, point b, point c) {
int r = (c.x - a.x) * (b.y - a.y) - (c.y - a.y) * (b.x - a.x);
if (r > 0)
return 1; //desno
else if (r < 0)
return -1; //levo
return 0;
}
bool inter(point a, point b, point c, point d) {
for (int i = 0;i < 2;i++) {
if (cross(a, b, c) == cross(a, b, d) || cross(a, b, c) == 0 || cross(a, b, d) == 0)
return false;
swap(a, c);
swap(b, d);
}
return true;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> n >> m >> e;
for (int i = 1;i <= n;i++) {
cin >> a[i].x >> a[i].y;
}
for (int i = 1;i <= m;i++) {
cin >> b[i].x >> b[i].y;
}
vector<pair<int, int>> edges(e);
for (int i = 0;i < e;i++) {
cin >> edges[i].f >> edges[i].s;
edge[edges[i].f][edges[i].s] = i + 1;
edge[edges[i].s][edges[i].f] = i + 1;
if (edges[i].f > edges[i].s)
swap(edges[i].f, edges[i].s);
}
for (int i = 1;i <= n;i++) {
for (int j = i + 1;j <= n;j++) {
if (edge[i][j])
continue;
int o = 1;
for (auto u : edges) {
o &= (!inter(a[i], a[j], a[u.f], a[u.s]));
}
if (o) {
edges.push_back({i, j});
edge[i][j] = edge[j][i] = (int)edges.size(); //fake edges
}
}
}
vector<int> v;
int node = 1, cnt = 0;
for (int i = 1;i <= n;i++) {
for (int j = i + 1;j <= n;j++) {
for (int k = j + 1;k <= n;k++) {
if (!edge[i][j] || !edge[i][k] || !edge[j][k])
continue;
int id = edge[i][j], id2 = edge[i][k], id3 = edge[j][k];
int o = 0;
for (int x = 1;x <= n;x++) {
int p = cross(a[i], a[j], a[x]);
int p1 = cross(a[k], a[i], a[x]);
int p2 = cross(a[j], a[k], a[x]);
o |= (p == p1 && p1 == p2);
}
if (o)
continue;
t[node].push_back(id);
t[node].push_back(id2);
t[node].push_back(id3);
f[id].push_back(node);
f[id2].push_back(node);
f[id3].push_back(node);
for (int x = 1;x <= m;x++) {
int p = cross(a[i], a[j], b[x]);
int p1 = cross(a[k], a[i], b[x]);
int p2 = cross(a[j], a[k], b[x]);
if (p == p1 && p1 == p2) {
v.push_back(node);
++cnt;
}
}
++node;
}
}
}
//> e su fake edgevi
if (cnt != m)
v.push_back(node);
for (int i = e;i < (int)edges.size();i++) {
if (f[i].size() == 2) {
g[f[i].front()].push_back(f[i].back());
g[f[i].back()].push_back(f[i].front());
}
else {
g[f[i].front()].push_back(node);
g[node].push_back(f[i].front());
}
}
vector<int> vis(node + 1);
function<void(int)> dfs = [&](int v) {
if (vis[v])
return;
vis[v] = 1;
for (auto u : g[v])
dfs(u);
};
for (auto u : v) {
if (!vis[u])
dfs(u);
}
if (vis[node]) {
for (int i = 1;i <= e;i++) {
if (f[i].size() == 1)
ans[i] = 1;
}
}
for (int i = 1;i <= node;i++) {
if (vis[i]) {
for (auto u : t[i]) {
if (u <= e)
ans[u] = 1;
}
}
}
for (int i = 1;i <= e;i++)
cout << ans[i];
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4376kb
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: 4368kb
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: 4412kb
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:
011111111111111111100001011000001001110111110111101011011001111110011011101111110111011101001000000001010100111111100110000100110100101101111111010011001111111100100011
result:
wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '011111111111111111100001011000...1111111010011001111111100100011'