QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#224315#7511. Planar GraphDAleksaWA 2ms4044kbC++145.1kb2023-10-23 01:13:052023-10-23 01:13:06

Judging History

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

  • [2023-10-23 01:13:06]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4044kb
  • [2023-10-23 01:13:05]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

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 * b.Y - a.Y * 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) {
    if(orientation(P, A, B) == 0) return orientation(P, B, C) == orientation(P, C, A);
    if(orientation(P, B, C) == 0) return orientation(P, C, A) == orientation(P, A, B);
    if(orientation(P, C, A) == 0) return orientation(P, A, B) == orientation(P, B, C);
    return orientation(P, A, B) == orientation(P, B, C) && orientation(P, B, C) == orientation(P, C, A);
}

struct edge {
    int u;
    int v;
};

const int N = 105;
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[3 * N];
bool target[N];
bool mark[N];

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;
}

int 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);
                ok = false;
                for(int i = 0; i < m; i++) {
                    if(in_triangle(b[i], a[x], a[y], a[z])) {
                        face[i] = id;
                        target[id] = true;
                        ok = true;
                        break;
                    }
                }
                if(!ok) target[0] = true;
            }
        }
    }
    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 < N; 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 < N; 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

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3956kb

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: 3952kb

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: 2ms
memory: 4044kb

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: -100
Wrong Answer
time: 1ms
memory: 3980kb

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:

00000000000000000000000000000000000001000000100000000100000001000000000000100000000000000001000000010000100000000000000100000000000000010000001000000000000000

result:

wrong answer 1st lines differ - expected: '000000000000000000000000000000...0000000000000001000000000000000', found: '000000000000000000000000000000...0000000010000001000000000000000'