QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225189#7511. Planar GraphDanilo21WA 16ms3788kbC++175.6kb2023-10-24 04:39:262023-10-24 04:39:26

Judging History

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

  • [2023-10-24 04:39:26]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:3788kb
  • [2023-10-24 04:39:26]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))

using namespace std;

struct Point{

    ll x, y;
    Point(ll x = 0, ll y = 0){ this->x = x; this->y = y; }
    void Read(){ cin >> x >> y; }

    Point operator+(const Point& a) const { return Point(x + a.x, y + a.y); }
    Point operator-(const Point& a) const { return Point(x - a.x, y - a.y); }
    ll operator*(const Point& a) const { return x*a.y - a.x*y; }

    bool OnSegment(array<Point, 2> a) const {
        ll x1 = min(a[0].x, a[1].x), x2 = max(a[0].x, a[1].x);
        ll y1 = min(a[0].y, a[1].y), y2 = max(a[0].y, a[1].y);
        return x > x1 && x < x2 && y > y1 && y < y2 && (*this - a[0]) * (a[1] - *this) == 0;
    }

    static int sig(ll x){ return x / max(abs(x), 1LL); }

    static bool Intersect(array<Point, 2> a, array<Point, 2> b){
        if (a[0].OnSegment(b) || a[1].OnSegment(b) || b[0].OnSegment(a) || b[1].OnSegment(a)) return 1;
        int o1 = sig((a[1] - a[0]) * (b[0] - a[1])) * sig((a[1] - a[0]) * (b[1] - a[1]));
        int o2 = sig((b[1] - b[0]) * (a[0] - b[1])) * sig((b[1] - b[0]) * (a[1] - b[1]));
        return o1 == -1 && o2 == -1;
    }

    bool Inside(Point a, Point b, Point c) const {
        if (OnSegment({a, b}) || OnSegment({b, c}) || OnSegment({c, a}))
            return 1;
        int o1 = sig((b - a) * (*this - b));
        int o2 = sig((c - b) * (*this - c));
        int o3 = sig((a - c) * (*this - a));
        return o1 == o2 && o2 == o3;
    }
};

const ll LINF = 4e18;
const int mxN = 110, INF = 2e9;
ll N, C, n, m, e, e1, comp[mxN*mxN];
Point p[mxN], q[mxN];
array<int, 2> E[mxN], E1[mxN*mxN];
array<int, 3> faces[mxN*mxN];
vector<int> g[mxN*mxN];
bool connected[mxN][mxN], vis[mxN*mxN], has[mxN*mxN];

void AddEdge(int u, int v){
    g[u].pb(v);
    g[v].pb(u);
}

void dfs(int s, int c){

    comp[s] = c;
    vis[s] = 1;
    for (int u : g[s])
        if (!vis[u]) dfs(u, c);
}

void Solve(){

    cin >> n >> m >> e;
    for (int i = 0; i < n; i++)
        p[i].Read();
    for (int i = 0; i < m; i++)
        q[i].Read();
    for (int i = 0; i < e; i++){
        cin >> E[i][0] >> E[i][1];
        E[i][0]--;
        E[i][1]--;
        connected[E[i][0]][E[i][1]] = 1;
        connected[E[i][1]][E[i][0]] = 1;
    }
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++){
            if (!connected[i][j]){
                bool f = 1;
                for (int k = 0; k < n; k++)
                    for (int l = k+1; l < n; l++)
                        if (i^k && j^k && i^l && j^l && connected[k][l] && Point::Intersect({p[i], p[j]}, {p[k], p[l]}))
                            f = 0;
                if (f){
                    connected[i][j] = 1;
                    connected[j][i] = 1;
                    E1[e1++] = {i, j};
                }
            }
        }
    }
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++){
            if (connected[i][j]){
                for (int k = j+1; k < n; k++){
                    if (connected[i][k] && connected[j][k]){
                        bool f = 1;
                        for (int l = 0; l < n; l++)
                            if (l^i && l^j && l^k && p[l].Inside(p[i], p[j], p[k]))
                                f = 0;
                        if (f) faces[N++] = {i, j, k};
                    }
                }
            }
        }
    }
    for (int i = 0; i < e1; i++){
        vector<int> idx;
        for (int j = 0; j < N; j++){
            int cnt = 0;
            for (int k = 0; k < 3; k++)
                if (faces[j][k] == E1[i][0] || faces[j][k] == E1[i][1])
                    cnt++;
            if (cnt == 2) idx.pb(j);
        }
        if (idx.size() == 1) idx.pb(N);
        AddEdge(idx[0], idx[1]);
    }
    for (int i = 0; i <= N; i++)
        if (!vis[i]) dfs(i, C++);
    for (int i = 0; i < m; i++){
        int idx = N;
        for (int j = 0; j < N; j++)
            if (q[i].Inside(p[faces[j][0]], p[faces[j][1]], p[faces[j][2]]))
                idx = j;
        has[comp[idx]] = 1;
    }
    for (int i = 0; i < e; i++){
        vector<int> v;
        for (int j = 0; j < N; j++){
            int cnt = 0;
            for (int k = 0; k < 3; k++)
                if (faces[j][k] == E[i][0] || faces[j][k] == E[i][1])
                    cnt++;
            if (cnt == 2) v.pb(comp[j]);
        }
        if (v.size() == 1) v.pb(comp[N]);
        cout << (has[v[0]] || has[v[1]]);
    }
    cout << en;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 3752kb

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: 16ms
memory: 3752kb

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:

001111111000111011100001010000001001010011010011101011001000100110011010001110010111011101001000000001010000101110100110000100100000101101011101100011000011111000000001

result:

wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '001111111000111011100001010000...1011101100011000011111000000001'