Cod sursa(job #2059884)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 7 noiembrie 2017 18:29:05
Problema Poligon Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 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);
}
int main()
{
    fscanf(f,"%d %d",&N,&M);
    for(int i=1;i<=N;i++)
    {
        fscanf(f,"%d %d",&P[i].first,&P[i].second);
        bands.push_back(P[i].first);
    }
    makeunique(bands);
    for(int i=0;i<bands.size();i++)
    {
        int x1,x2;
        x1=bands[i];x2=(i==bands.size()-1 ? 1000000: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<=x2&&P2.first>=x1)
            {
                V[i].push_back(make_pair(P1,P2));
            }
        }
    }
    for(int i=1;i<=M;i++)
    {
        int x,y;
        fscanf(f,"%d %d",&x,&y);
        int st=0,dr=bands.size()-1;
        while(st<dr)
        {
            int mid=(st+dr+1)/2;
            if(bands[mid]>x)dr=mid-1;
            else st=mid;
        }
        bool ok=0;
        for(auto it:V[st])
            if(in(it.first,it.second,{x,y})&&inclus(it.first,it.second,{x,y}))
            {
                ok=1;break;
            }
        if(ok){rez++;continue;}
        for(auto it:V[st])
            if(it.first.first==it.second.first)continue;
            else if(((it.first.first==x&&it.second.first<it.first.first&&it.first.second<=y)||(it.second.first==x&&it.second.first>it.first.first&&it.second.second<=y)))ok^=1;
            else if(it.first.first!=x&&it.second.first!=x&&in(it.first,it.second,{x,y})&&eval(it.first,it.second,x)<=y)
                ok^=1;
        rez+=ok;
//        printf("%d %d\n",i,ok);
    }
    fprintf(g,"%d",rez);
    fclose(f);
    fclose(g);
    return 0;
}