oj.uz

Submission #230804

# Submission time Handle Problem Language Result Execution time Memory
230804 2020-05-11T20:23:46 Z walnutwaldo20 Relay (COI16_relay) C++14
18 / 100
 2000 ms 4200 KB 
#include <bits/stdc++.h>

#define F0R(i, a) for (int i = 0; i < (int)(a); i++)

#define PB push_back
#define MP make_pair
#define X real()
#define Y imag()

#define F first
#define S second

using namespace std;

typedef long long ll;
typedef complex<ll> point;
typedef pair<point, point> edge;

#define MAXN 100000

bool prereaches[MAXN];
bool reaches[MAXN];

edge rev(edge e) { return MP(e.S, e.F); }

ll sign(ll l) {
    if (l < 0) {
        return -1;
    }
    if (l == 0) {
        return 0;
    }
    return 1;
}

ll crossp(point p1, point p2) {
    return (conj(p1) * p2).Y;
}

bool rightof(point p, edge e) {
    bool ret = crossp(e.S - e.F, p - e.S) <= 0;
    return ret;
}

bool oppositesides(edge e1, edge e2) {
    return sign(crossp(e1.F - e1.S, e2.F - e1.F)) * sign(crossp(e1.F - e1.S, e2.S - e1.F)) == -1;
}

bool intersects(edge e1, edge e2) {
    return oppositesides(e1, e2) && oppositesides(e2, e1);
}

point get(vector<point>& v, int idx) {
    return v[(idx % (int)v.size() + (int)v.size()) % (int)v.size()];
}

void read(int& len, vector<point>& vec) {
    cin >> len;
    F0R(i, len) {
        ll x, y;
        cin >> x >> y;
        vec.PB(point(x, y));
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    vector<point> v, hull;
    read(n, v);
    read(m, hull);
    
    F0R(i, n) {
        bool works = true;
        F0R(j, m) if (intersects(MP(v[i], v[0]), MP(get(hull, j), get(hull, j + 1)))) {
            works = false;
        }
        if (works) {
            prereaches[i] = true;
        }
    }
    F0R(s, n) if (prereaches[s]) {
        F0R(i, n) {
            bool works = true;
            F0R(j, m) if (intersects(MP(v[i], v[s]), MP(get(hull, j), get(hull, j + 1)))) {
                works = false;
            }
            if (works) {
                reaches[i] = true;
            }
        }
    }
    
    int res = 0;
    F0R(i, n) if (reaches[i]) {
        res++;
    }
    cout << res - 1 << endl;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 508 KB Output is correct
2 Correct 118 ms 384 KB Output is correct
3 Correct 63 ms 384 KB Output is correct
4 Correct 157 ms 404 KB Output is correct
5 Correct 73 ms 384 KB Output is correct
6 Correct 77 ms 504 KB Output is correct
7 Correct 154 ms 384 KB Output is correct
8 Correct 84 ms 512 KB Output is correct
9 Correct 23 ms 384 KB Output is correct
10 Correct 25 ms 384 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 508 KB Output is correct
2 Correct 118 ms 384 KB Output is correct
3 Correct 63 ms 384 KB Output is correct
4 Correct 157 ms 404 KB Output is correct
5 Correct 73 ms 384 KB Output is correct
6 Correct 77 ms 504 KB Output is correct
7 Correct 154 ms 384 KB Output is correct
8 Correct 84 ms 512 KB Output is correct
9 Correct 23 ms 384 KB Output is correct
10 Correct 25 ms 384 KB Output is correct
11 Execution timed out 2085 ms 760 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 508 KB Output is correct
2 Correct 118 ms 384 KB Output is correct
3 Correct 63 ms 384 KB Output is correct
4 Correct 157 ms 404 KB Output is correct
5 Correct 73 ms 384 KB Output is correct
6 Correct 77 ms 504 KB Output is correct
7 Correct 154 ms 384 KB Output is correct
8 Correct 84 ms 512 KB Output is correct
9 Correct 23 ms 384 KB Output is correct
10 Correct 25 ms 384 KB Output is correct
11 Execution timed out 2084 ms 4200 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 508 KB Output is correct
2 Correct 118 ms 384 KB Output is correct
3 Correct 63 ms 384 KB Output is correct
4 Correct 157 ms 404 KB Output is correct
5 Correct 73 ms 384 KB Output is correct
6 Correct 77 ms 504 KB Output is correct
7 Correct 154 ms 384 KB Output is correct
8 Correct 84 ms 512 KB Output is correct
9 Correct 23 ms 384 KB Output is correct
10 Correct 25 ms 384 KB Output is correct
11 Execution timed out 2085 ms 760 KB Time limit exceeded
12 Halted 0 ms 0 KB -