Submission #230804

#	Time	Username	Problem	Language	Result	Execution time	Memory
230804		walnutwaldo20	Relay (COI16_relay)	C++14	18 / 100	2085 ms	4200 KiB

relay

#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 / 18
• Subtask 2: 0 / 19
• Subtask 3: 0 / 20
• Subtask 4: 0 / 43