제출 #1344159

#제출 시각아이디문제언어결과실행 시간메모리
1344159gkos5678Relay (COI16_relay)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

#define lb lower_bound
#define ff first
#define ss second

typedef long long ll;
typedef pair<ll, ll> pll;

const int maxn = 1e5 + 7;

ll n, m, a[maxn], r[maxn], ps[maxn];
pll o[maxn], b[maxn], pv, c1;
bool in[maxn];
set<int> fr;

ll ccw(pll a, pll b, pll c){
    return a.ff * (b.ss - c.ss) + b.ff * (c.ss - a.ss) + c.ff * (a.ss - b.ss);
}

bool comp(pll a, pll b){
    if ((a.ss >= pv.ss) != (b.ss >= pv.ss))
        return (a.ss > b.ss);
    ll f = ccw(pv, a, b);
    if (f != 0) return (f > 0);
    if ((a.ff > pv.ff) != (b.ff > pv.ff))
        return (a.ff > b.ff);
    return (a.ff < b.ff);
}

bool insi(int l1, int r1, int gr){
    if ((l1 <= gr && gr <= r1) || (l1 <= (gr + m) && (gr + m) <= r1))
        return 1;
    return 0;
}

bool inters(int l1, int r1, int l2, int r2){
    if (insi(l1, r1, l2) || insi(l1, r1, r2))
        return 1;
    return 0;
}

int main(){
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++){
        a[i] = r[i] = -1;
        cin >> b[i].ff >> b[i].ss;
    }
    c1 = b[0];
    cin >> m;
    for (int i = 0; i < m; i++){
        fr.insert(i);
        fr.insert(i + m);
        cin >> o[i].ff >> o[i].ss;
    }
    pv = o[0];
    sort(b, b + n, comp);
    int trs, le = 0, ri = 1;
    in[0] = 1;
    for (int i = 0; i < m; i++){
        if (ccw(b[0], o[(i + 1) % m], o[i]) >= 0){
            trs = i;
            a[0] = i;
            break;
        }
    }
    while(le != ri){
        le = (le + n - 1) % n;
        if (ccw(b[le], o[(trs + 1) % m], o[trs]) < 0)
            break;
        in[le] = 1;
        a[le] = trs;
    }
    le = (le + 1) % n;
    while(ri != le){
        if (ccw(b[ri], o[(trs + 1) % m], o[trs]) < 0)
            break;
        in[ri] = 1;
        a[ri] = trs;
        ri = (ri + 1) % n;
    }

    for (int i = (trs + 1) % m; i != trs; i = (i + 1) % m){
        while(le != ri){
            if (ccw(b[le], o[(i + 1) % m], o[i]) >= 0)
                break;
            r[le] = i;
            le = (le + 1) % n;
        }
        if (le == ri){
            a[ri] = i;
            ri = (ri + 1) % n;
        }
        while(ri != le){
            if (ccw(b[ri], o[(i + 1) % m], o[i]) < 0)
                break;
            a[ri] = i;
            ri = (ri + 1) % n;
        }
    }
    for (int i = 0; i < n; i++){
        if (r[i] == -1)
            r[i] = trs;
        r[i] = (r[i] + m - 1) % m;
        if (r[i] < a[i])
            r[i] += m;
    }

    int ind;
    for (int i = 0; i < n; i++)
        if (b[i] == c1)
            ind = i;
    for (int i = 0; i < n; i++){
        if (!inters(a[i], r[i], a[ind], r[ind])) continue;
        while(!fr.empty() && fr.lb(a[i]) != fr.end() && *fr.lb(a[i]) <= r[i]){
            int lbb = *fr.lb(a[i]) % m;
            fr.erase(fr.find(lbb));
            fr.erase(fr.find(lbb + m));
            ps[lbb] = 1;
        }
    }
    for (int i = 1; i < m; i++)
        ps[i] += ps[i - 1];

    int ans = -1;
    for (int i = 0; i < n; i++){
        int uk = ps[r[i] % m];
        if (a[i] > 0) uk -= ps[a[i] - 1];
        if (uk < 0) uk += ps[m - 1];
        ans += (uk > 0);
    }
    cout << ans << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...