Cod sursa(job #2060065)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 7 noiembrie 2017 20:31:33
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.81 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
FILE *f=fopen("poligon.in","r");
FILE *g=fopen("poligon.out","w");
void makeunique(vector<int> &V)
{
    sort(V.begin(),V.end());
    vector<int> :: iterator it=unique(V.begin(),V.end());
    V.resize(distance(V.begin(),it));
}
int N,M,rez;
vector<int> bands;
vector<pair<pair<int,int>,pair<int,int> > > V[805];
pair<int,int> P[805];
bool inclus(pair<int,int> a,pair<int,int> b,pair<int,int> c)
{
    return (1LL*a.first*b.second+1LL*b.first*c.second+1LL*c.first*a.second-1LL*a.first*c.second-1LL*b.first*a.second-1LL*c.first*b.second)==0;
}
double eval(pair<double,double> a,pair<double,double> b,double x)
{
    return a.second+((b.second-a.second)/(b.first-a.first))*(x-a.first);
}
bool in(pair<int,int> a,pair<int,int> b,pair<int,int> c)
{
    if(a.first!=b.first)return min(a.first,b.first)<=c.first&&c.first<=max(a.first,b.first);
    return c.first==a.first&&min(a.second,b.second)<=c.second&&c.second<=max(a.second,b.second);
}
const int LEN=10000;
int ind=LEN-1;
char buff[LEN];
int i32()
{
    int rez=0,sgn=1;
    while((buff[ind]<'0'||buff[ind]>'9')&&buff[ind]!='-')
    {
        if(++ind>=LEN)
        {
            ind=0;
            fread(buff,1,LEN,f);
        }
    }
    if(buff[ind]=='-')
    {
        sgn=-1;
        if(++ind>=LEN)
        {
            ind=0;
            fread(buff,1,LEN,f);
        }
    }
    while(buff[ind]>='0'&&buff[ind]<='9')
    {
        rez=rez*10+buff[ind]-'0';
        if(++ind>=LEN)
        {
            ind=0;
            fread(buff,1,LEN,f);
        }
    }
    return rez*sgn;
}
bool cmp(pair<pair<int,int>,pair<int,int> > a,pair<pair<int,int>,pair<int,int> > b)
{
    return a.first.second+a.second.second<=b.first.second+b.second.second;
}
int da(pair<int,int> a,pair<int,int> b,pair<int,int> c)
{
    if(a>b)swap(a,b);
    long long expr=(1LL*a.first*b.second+1LL*b.first*c.second+1LL*c.first*a.second-1LL*a.first*c.second-1LL*b.first*a.second-1LL*c.first*b.second);
    if(expr==0)return 0;
    return expr<0 ? -1:1;
}
int main()
{
    N=i32();M=i32();
    for(int i=1;i<=N;i++)
    {
        P[i].first=i32();P[i].second=i32();
        bands.push_back(P[i].first);
    }
    makeunique(bands);
    for(int i=0;i<bands.size()-1;i++)
    {
        int x1,x2;
        x1=bands[i];x2=bands[i+1];
        for(int j=1;j<=N;j++)
        {
            pair<int,int> P1=P[j],P2=P[j%N+1];
            if(P1>P2)swap(P1,P2);
            if(P1.first<=x1&&P2.first>=x2)
            {
                P1.second=eval(P1,P2,max(P1.first,x1));P1.first=max(P1.first,x1);
                P2.second=eval(P1,P2,min(P2.first,x2));P2.first=min(P2.first,x2);
                V[i].push_back(make_pair(P1,P2));
            }
        }
        V[i].push_back({{-100,-100},{-100,-100}});
        sort(V[i].begin(),V[i].end());
    }
    for(int i=1;i<=M;i++)
    {
        int x,y;
        x=i32();y=i32();
        if(bands[0]>x||bands.back()<x)continue;
        int st=0,dr=bands.size()-2;
        while(st<dr)
        {
            int mid=(st+dr+1)/2;
            if(bands[mid]>x)dr=mid-1;
            else st=mid;
        }
        if(st&&bands[st-1]==bands[st])st--;
        int ind=st;
        st=0;dr=V[ind].size()-1;
        while(st<dr)
        {
            int mid=(st+dr+1)/2;
            if(da(V[ind][mid].first,V[ind][mid].second,{x,y})==0)
            {
                st=1;break;
            }
            else if(da(V[ind][mid].first,V[ind][mid].second,{x,y})>0)
            {
                st=mid;
            }
            else
            {
                dr=mid-1;
            }
        }
        rez+=(st&1);
        ///printf("%d %d\n",i,(st&1));
    }
    fprintf(g,"%d",rez);
    fclose(f);
    fclose(g);
    return 0;
}