Cod sursa(job #2059104)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 6 noiembrie 2017 17:34:31
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 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);
}
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++)
    {
        for(int j=1;j<=N;j++)
        {
            if(min(P[j].first,P[j%N+1].first)<=bands[i]&&bands[i]<=max(P[j].first,P[j%N+1].first))
            {
                V[i].push_back(make_pair(P[j],P[j%N+1]));
            }
        }
    }
    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)st=mid;
            else dr=mid-1;
        }
        int nr=0;
        bool ok=0;
        for(auto it:V[st])
        {
            if(it.first.first==it.second.first)
            {
                if(x==it.first.first&&min(it.first.second,it.second.second)<=y&&y<=max(it.first.second,it.second.second))ok=1;
            }
            else
            {
                if(inclus(it.first,it.second,make_pair(x,y)))ok=1;
                else
                {
                    if(it.first.first==x&&it.first.first>it.second.first)nr++;
                    else if(it.second.first==x&&it.first.first<it.second.first)nr++;
                    else
                    {
                        if(eval(it.first,it.second,x)<=y)nr++;
                    }
                }
            }
        }
        if(ok||nr%2==1)rez++;
    }
    fprintf(g,"%d",rez);
    fclose(f);
    fclose(g);
    return 0;
}