Submission #1344240

#TimeUsernameProblemLanguageResultExecution timeMemory
1344240gkos5678Relay (COI16_relay)C++20
0 / 100
1 ms344 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 = 1e5 + 7;

ll n, m;
pll o[maxn], b[maxn];
bool b1[maxn], b2[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;

    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++)
            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...