QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226261 | #7511. Planar Graph | SolitaryDream# | WA | 1ms | 3556kb | C++17 | 2.8kb | 2023-10-25 19:10:39 | 2023-10-25 19:10:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 305;
struct P {
int x, y;
int Phase() {
if (y != 0) return y > 0 ? 0 : 1;
return x > 0 ? 0 : 1;
}
};
P operator+(P u, P v) { return {u.x + v.x, u.y + v.y}; }
P operator-(P u, P v) { return {u.x - v.x, u.y - v.y}; }
int Det(P u, P v) { return u.x * v.y - u.y * v.x; }
int n, m, e;
P bp[N], sp[N];
vector<pii> g[N];
inline int Intersect(P x, P u, P v) {
if (u.Phase() == v.Phase()) return 0;
if (u.Phase() == 0) swap(u, v);
return Det(v - u, x - u) > 0;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> e;
for (int i = 1; i <= n; ++i) cin >> bp[i].x >> bp[i].y;
for (int i = 1; i <= m; ++i) cin >> sp[i].x >> sp[i].y;
for (int i = 0, x, y; i < e; ++i) {
cin >> x >> y;
g[x].push_back({y, i << 1});
g[y].push_back({x, i << 1 | 1});
}
for (int i = 1; i <= n; ++i) {
sort(g[i].begin(), g[i].end(), [&](pii u, pii v) {
P vecu = bp[u.first] - bp[i];
P vecv = bp[v.first] - bp[i];
int du = vecu.Phase();
int dv = vecv.Phase();
if (du != dv) return du < dv;
return Det(vecu, vecv) > 0;
});
}
string ans(e, '0');
vector<bool> vis(e << 1);
for (int x = 1; x <= n; ++x) {
for (auto [y, id] : g[x]) if (!vis[id]) {
vector<P> pts(2);
vector<int> eds(1);
pts[0] = bp[x]; pts[1] = bp[y];
eds[0] = id;
vis[id] = 1;
for (int nx = y, la = x, la_id = id; ; ) {
int k = find(g[nx].begin(), g[nx].end(), pii(la, la_id ^ 1)) - g[nx].begin();
k = (k + g[nx].size() - 1) % g[nx].size();
auto [nnx, nid] = g[nx][k];
vis[nid] = 1;
eds.push_back(nid);
pts.push_back(bp[nnx]);
if (nnx == x) break;
la = nx; nx = nnx; la_id = nid;
}
// for (auto [x, y] : pts) cerr << "(" << x << ' ' << y << ')';
// cerr << endl;
int area = 0;
for (int i = 0; i + 1 < pts.size(); ++i) area += Det(pts[i], pts[i + 1]);
for (int i = 1; i <= m; ++i) {
P cur = sp[i];
int cnt = (area < 0 ? 1 : 0);
for (int j = 0; j + 1 < pts.size(); ++j) {
if (Intersect(cur, pts[j], pts[j + 1])) ++cnt;
}
if (cnt & 1) {
for (auto x : eds) ans[x >> 1] = '1';
break;
}
}
}
}
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3428kb
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: 3500kb
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: 0ms
memory: 3556kb
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:
001000011010111000001001000000001000000011011001001010010001001100110000000010100110010110000001010010011101000010110110000100100100101100111100110001100000011000110011
result:
wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '001000011010111000001001000000...0111100110001100000011000110011'