제출 #1344239

#제출 시각아이디문제언어결과실행 시간메모리
1344239gkos5678Relay (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], b1[maxn], b2[maxn], okd[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++)
        cin >> o[i].ff >> o[i].ss;

    b1[0] = 1;
    for (int it : {0, 1}){
        for (int i = 0; i < n; i++) b2[i] = okd[i] = 0;
        for (int i = 0; i < n; i++){
            if (!b1[i]) continue;
            for (int j = 0; j < m; j++)
                okd[j] |= (ccw(b[i], o[(j + 1) % m], o[j]) >= 0);
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                b2[i] |= (ccw(b[i], o[(j + 1) % m], o[j]) >= 0 && okd[j]);
        for (int i = 0; i < n; i++)
            b1[i] = b2[i];
    }

    int ans = 0;
    for (int i = 1; i < n; i++)
        ans += b1[i];
    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...