Cod sursa(job #2312090)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 4 ianuarie 2019 10:45:21
Problema Poligon Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
FILE *f=fopen("poligon.in","r");
FILE *g=fopen("poligon.out","w");
pair<int,int> P[805];
vector<int> V[805];
int t[805];
int N,M,col,R;
double mij;
long long det(pair<int,int> a,pair<int,int> b,pair<int,int> c)
{
    return 1LL*a.x*b.y+1LL*b.x*c.y+1LL*c.x*a.y-1LL*a.x*c.y-1LL*b.x*a.y-1LL*c.x*b.y;
}
double eval(pair<int,int> a,pair<int,int> b,double x)
{
    return a.y+(b.y-a.y)*(mij-a.x)/((double)b.x-a.x);
}
bool cmp(int a,int b)
{
    return eval(P[a],P[a+1],mij)<eval(P[b],P[b+1],mij);
}
bool ok(int i,pair<int,int> a)
{
    long long tmp=det(min(P[i],P[i+1]),max(P[i],P[i+1]),a);
    if(tmp==0){col=1;return 1;}
    return tmp>0;
}
int main()
{
    fscanf(f,"%d%d",&N,&M);
    for(int i=1;i<=N;i++){fscanf(f,"%d %d",&P[i].x,&P[i].y);t[i]=P[i].x;}
    P[N+1]=P[1];
    t[0]=-1;
    sort(t+1,t+1+N);
    int k=0;
    for(int i=1;i<=N;i++)
        if(t[k]!=t[i])
            t[++k]=t[i];
    t[k+1]=t[k]+100;
    for(int i=1;i<=k;i++)
    {
        for(int j=1;j<=N;j++)
        {
            if((P[j].x<=t[i]&&t[i+1]<=P[j+1].x)||(P[j+1].x<=t[i]&&t[i+1]<=P[j].x))
                V[i].push_back(j);
        }
        mij=0.5*(t[i]+t[i+1]);
        sort(V[i].begin(),V[i].end(),cmp);
    }
    for(int i=1;i<=M;i++)
    {
        pair<int,int> p;
        fscanf(f,"%d %d",&p.x,&p.y);
        int pos=0;
        for(int pas=1<<9;pas;pas>>=1)
            if(pos+pas<=k&&t[pos+pas]<p.x)
                pos+=pas;
        int rez=-1;
        col=0;
        for(int pas=1<<9;pas;pas>>=1)
            if(rez+pas<V[pos].size()&&ok(V[pos][rez+pas],p))
                rez+=pas;
        rez++;
        R+=(rez%2||col);
    }
    fprintf(g,"%d",R);
    fclose(f);
    fclose(g);
    return 0;
}