Cod sursa(job #1756352)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 12 septembrie 2016 18:04:29
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>

#define MAXN 800
#define x first
#define y second

using namespace std;

vector <int> v[MAXN];
pair <int, int> a[MAXN+1];
int k, u, n, t[MAXN];
bool colin;

inline long long arie(pair <int, int> a, pair <int, int> b, pair <int, int> c){
    return 1LL*a.x*b.y-1LL*a.y*b.x+1LL*b.x*c.y-1LL*b.y*c.x+1LL*c.x*a.y-1LL*c.y*a.x;
}

inline bool ok(int p, pair <int, int> e){
    long long r;
    if(a[p].x<a[p+1].x) r=arie(a[p], a[p+1], e);
    else r=arie(a[p+1], a[p], e);
    if(r==0) colin=1;
    return (r>0);
}

inline double intersect(pair <int, int> p, pair <int, int> q){
    return p.y+1LL*(q.y-p.y)*(u-p.x)/(double)(q.x-p.x);
}

bool cmp(const int p, const int q){
    return intersect(a[p], a[p+1])<intersect(a[q], a[q+1]);
}

inline void precalc(){
    sort(t, t+n);
    k=1;
    for(int i=1; i<n; i++)
        if(t[i]!=t[k-1])
            t[k++]=t[i];
    for(int i=0; i<k; i++){
        for(int j=0; j<n; j++)
            if(((a[j].x<=t[i])&&(t[i]<a[j+1].x))||((a[j+1].x<=t[i])&&(t[i]<a[j].x)))
                v[i].push_back(j);
        u=t[i];
        sort(v[i].begin(), v[i].end(), cmp);
    }
}

inline bool calc(pair <int, int> q){
    if((q.x<t[0])||(q.x>t[k-1])) return false;
    int rez=0, poz=-1;
    colin=0;
    for(int pas=1<<9; pas; pas>>=1)
        if((rez+pas<k)&&(t[rez+pas]<q.x))
            rez+=pas;
    for(int pas=1<<9; pas; pas>>=1)
        if((poz+pas<(int)v[rez].size())&&(ok(v[rez][poz+pas], q)))
            poz+=pas;
    return ((colin)||((poz+1)%2));
}

int main(){
    int m, ans;
    pair <int, int> q;
    FILE *fin, *fout;
    fin=fopen("poligon.in", "r");
    fout=fopen("poligon.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(int i=0; i<n; i++){
        fscanf(fin, "%d%d", &a[i].x, &a[i].y);
        t[i]=a[i].x;
    }
    a[n]=a[0];
    precalc();
    ans=0;
    for(int i=0; i<m; i++){
        fscanf(fin, "%d%d", &q.x, &q.y);
        ans+=calc(q);
    }
    fprintf(fout, "%d\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}