Cod sursa(job #2233624)

Utilizator AlexandruRudiAlexandru Rudi AlexandruRudi Data 23 august 2018 19:01:43
Problema Poligon Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define pb push_back
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005
#define x1 xdddddddddddddddddd
#define y1 ydddddddddddddddddd

int n,m,ans;

ll x,y;

pl a[805];

int nxt(int p){
    p++;
    if(p==n+1) p=1;
    return p;
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    ifstream cin("poligon.in");
    ofstream cout("poligon.out");
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> a[i].x >> a[i].y;
    }
    for(int i=1;i<=m;i++){
        cin >> x >> y;
        int f=1;
        while(a[f].y==y) f++;
        rotate(a+1,a+f,a+n+1);
        int fd=0,cnt=0;
        for(int j=1;j<=n;j++){
            ll p=min(a[j].y,a[nxt(j)].y);
            ll q=max(a[j].y,a[nxt(j)].y);
            if(q<=y || p>=y) continue;
            ll s=min(a[j].x,a[nxt(j)].x);
            ll t=max(a[j].x,a[nxt(j)].x);
            if(t*(y-p)+s*(q-y)==x*(q-p)){
                ans++; fd=1;
                break;
            }
            else if(t*(y-p)+s*(q-y)<x*(q-p)) cnt++;
        }
        if(fd) continue; fd=0;
        for(int j=2;j<=n;j++){
            if(a[j].y!=y) continue;
            int k=j;
            while(k<=n && a[k].y==y) k++;
            k--;
            ll s=min(a[j].x,a[k].x);
            ll t=max(a[j].x,a[k].x);
            if(s<=x && x<=t){
                ans++;
                fd=1;
                break;
            }
            ll p=min(a[j-1].y,a[nxt(k)].y);
            ll q=max(a[j-1].y,a[nxt(k)].y);
            if(p<y && q>y && t<x) cnt++;
            j=k;
        }
        if(fd) continue;
        if(cnt%2) ans++;
    }
    cout << ans;
}