Cod sursa(job #2059155)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 6 noiembrie 2017 18:40:41
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 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++)
    {
        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);
        if(x<bands[0]||x>bands.back())continue;
        int st=0,dr=bands.size()-1;
        while(st<dr)
        {
            int mid=(st+dr)/2;
            if(bands[mid]<x)st=mid+1;
            else dr=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(in(it.first,it.second,{x,y})&&eval(it.first,it.second,x)>=y)
                ok^=1;
        rez+=ok;
    }
    fprintf(g,"%d",rez);
    fclose(f);
    fclose(g);
    return 0;
}