QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226261#7511. Planar GraphSolitaryDream#WA 1ms3556kbC++172.8kb2023-10-25 19:10:392023-10-25 19:10:39

Judging History

你现在查看的是最新测评结果

  • [2023-10-25 19:10:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3556kb
  • [2023-10-25 19:10:39]
  • 提交

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'