제출 #1344258

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

#define ff first
#define ss second

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

const int maxn = 3005;

ll n, m, t1[maxn], t2[maxn];
pll o[maxn], b[maxn];
bool b1[maxn], b2[maxn], c[maxn][maxn], okd[maxn];

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);
}

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

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> b[i].ff >> b[i].ss;
    cin >> m;
    for (int i = 0; i < m; i++)
        cin >> o[i].ff >> o[i].ss;

    for (int i = 0; i < n; i++){
        t1[i] = t2[i] = -1;
        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)
                t2[i] = (j + 1) % m;
            if (tr < 0 && slj >= 0)
                t1[i] = (j + 1) % m;
        }
    }
    b1[0] = 1;
    for (int it : {0, 1}){
        for (int i = 0; i < max(n, m); 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++){
            for (int j = 0; j < n; j++){
                if (!b1[j]) continue;
                b2[i] |= (ccw(b[i], b[j], o[t1[j]]) >= 0 || ccw(b[i], o[t2[j]], b[j]) >= 0);
            }
        }
        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...