QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226299 | #7511. Planar Graph | SolitaryDream# | WA | 1ms | 3576kb | C++17 | 3.7kb | 2023-10-25 19:44:59 | 2023-10-25 19:44:59 |
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];
P edg_mp[N];
int edg_hs[N][2], sp_hs[N];
vector<pii> g[N];
inline int Intersect(P x, P u, P v) {
if ((u - x).Phase() == (v - x).Phase()) return 0;
if ((u - x).Phase() == 0) swap(u, v);
return Det(v - u, x - u) > 0;
}
inline int Inside(P cur, const vector<P> &pts) {
int area = 0;
for (int i = 0; i + 1 < pts.size(); ++i) area += Det(pts[i], pts[i + 1]);
int cnt = (area < 0 ? 1 : 0);
for (int j = 0; j + 1 < pts.size(); ++j) {
if (Intersect(cur, pts[j], pts[j + 1])) ++cnt;
}
return cnt & 1;
}
mt19937 rd(1025);
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;
bp[i].x *= 2; bp[i].y *= 2;
}
for (int i = 1; i <= m; ++i) {
cin >> sp[i].x >> sp[i].y;
sp[i].x *= 2; sp[i].y *= 2;
}
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});
edg_mp[i] = bp[x] + bp[y];
edg_mp[i].x /= 2; edg_mp[i].y /= 2;
}
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;
});
}
vector<int> vis(e << 1);
for (int x = 1, ts = 0; x <= n; ++x) {
for (auto [y, id] : g[x]) if (!vis[id]) {
++ts;
vector<P> pts(2);
vector<int> eds(1);
pts[0] = bp[x]; pts[1] = bp[y];
eds[0] = id;
vis[id] = ts;
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] = ts;
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 cur_hash = rd();
for (int i = 1; i <= m; ++i) if (Inside(sp[i], pts)) sp_hs[i] ^= cur_hash;
for (int i = 0; i < e; ++i) {
bool is_on = 0;
if (vis[i << 1] == ts) {
is_on = 1;
edg_hs[i][0] ^= cur_hash;
}
if (vis[i << 1 | 1] == ts) {
is_on = 1;
edg_hs[i][1] ^= cur_hash;
}
if (!is_on && Inside(edg_mp[i], pts)) {
edg_hs[i][0] ^= cur_hash;
edg_hs[i][1] ^= cur_hash;
}
}
}
}
set<int> st;
for (int i = 1; i <= m; ++i) st.insert(sp_hs[i]);
string ans(e, '0');
for (int i = 0; i < e; ++i) if (st.count(edg_hs[i][0]) || st.count(edg_hs[i][1])) ans[i] = '1';
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
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: 3472kb
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: 1ms
memory: 3528kb
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: 1ms
memory: 3488kb
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: 1ms
memory: 3528kb
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: -100
Wrong Answer
time: 1ms
memory: 3576kb
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:
000110010001001101100010110101100100011110011110110101010100110011111010101110101001001011100000010101000100010011100100100110100001011010001010001010000100011000001101010110011001101111010000011001000011
result:
wrong answer 1st lines differ - expected: '000110010001001101100010110101...0011001101111010000011001000011', found: '000110010001001101100010110101...0011001101111010000011001000011'