제출 #1344208

#제출 시각아이디문제언어결과실행 시간메모리
1344208gkos5678Relay (COI16_relay)C++20
0 / 100
1 ms348 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;
    }
    cin >> m;
    for (int i = 0; i < m; i++){
        fr.insert(i);
        fr.insert(i + m);
        cin >> o[i].ff >> o[i].ss;
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            ll tr = ccw(b[i], o[(j + 1) % m], o[j]), slj = ccw(b[i], o[(j + 2) % m], o[(j + 1) % m]);
            if (tr < 0 && slj >= 0)
                a[i] = j + 1;
            if (tr >= 0 && slj < 0)
                r[i] = j;
        }
        if (r[i] < a[i]) r[i] += m;
    }
    for (int i = 0; i < n; i++){
        if (!inters(a[i], r[i], a[0], r[0])) 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...