Cod sursa(job #1756178)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 12 septembrie 2016 02:22:21
Problema Poligon Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

#define EPS 0.0000001
#define MAXN 800

struct mycreation{
    double x, y;
}a[MAXN+1];

double t[MAXN], k;

std::vector<int>v[MAXN];

const double alfa=0.5982673;

inline double arie(int p, mycreation e){
    int q=p+1;
    if(a[p].x>a[q].x){
        int aux=p;
        p=q;
        q=aux;
    }
    return a[p].x*a[q].y-a[q].x*a[p].y+a[q].x*e.y-e.x*a[q].y+e.x*a[p].y-a[p].x*e.y;
}

inline double intersection(mycreation p, mycreation q){
    return p.y+(q.y-p.y)*(k-p.x)/(q.x-p.x);
}

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

inline mycreation rotim(mycreation a){
    double x=a.x, y=a.y;
    a.x=x*cos(alfa)-y*sin(alfa);
    a.y=x*sin(alfa)+y*cos(alfa);
    return a;
}

int main(){
    int ans, n, m, rez, poz;
    mycreation 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, "%lf%lf", &a[i].x, &a[i].y);
        a[i]=rotim(a[i]);
        t[i]=a[i].x;
    }
    a[n]=a[0];
    std::sort(t, t+n);
    for(int i=1; i<n; i++){
        for(int j=0; j<n; j++)
            if(((a[j].x<t[i-1]+EPS)&&(t[i]<a[j+1].x+EPS))||((a[j+1].x<t[i-1]+EPS)&&(t[i]<a[j].x+EPS)))
                v[i].push_back(j);
        k=t[i];
        std::sort(v[i].begin(), v[i].end(), cmp);
    }
    ans=0;
    for(int i=0; i<m; i++){
        fscanf(fin, "%lf%lf", &q.x, &q.y);
        q=rotim(q);
        if((t[0]<q.x+EPS)&&(q.x<t[n-1]+EPS)){
            rez=0;
            for(int pas=1<<9; pas; pas>>=1)
                if((rez+pas<n)&&(t[rez+pas]<q.x-EPS))
                    rez+=pas;
            rez++;
            if((q.x-t[rez]>-EPS)&&(q.x-t[rez]<EPS)) ans++;
            else{
                poz=-1;
                for(int pas=1<<9; pas; pas>>=1)
                    if((poz+pas<(int)v[rez].size())&&(arie(v[rez][poz+pas], q)>-EPS))
                        poz+=pas;
                if(poz>=0){
                    if(arie(v[rez][poz], q)<EPS) ans++;
                    else ans+=(poz+1)%2;
                }
            }
        }
    }
    fprintf(fout, "%d\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}