Cod sursa(job #2060569)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 8 noiembrie 2017 14:49:50
Problema Poligon Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
FILE *f=fopen("poligon.in","r");
FILE *g=fopen("poligon.out","w");
pair<double,double> P[805];
vector<int> bands;
vector<pair<pair<double,double>,pair<double,double> > > V[805];
///belit pt puncte care se afla pe o latura verticala
///fix later
int N,M,rez;
bool cmp(pair<pair<double,double>,pair<double,double> > a,pair<pair<double,double>,pair<double,double> > b)
{
    return a.first.second+a.second.second<b.first.second+b.second.second;
}
double det(pair<double,double> a,pair<double,double> b,pair<double,double> c)
{
    return a.first*b.second+b.first*c.second+c.first*a.second-a.first*c.second-b.first*a.second-c.first*b.second;
}
int main()
{
    fscanf(f,"%d %d",&N,&M);
    for(int i=1;i<=N;i++)
    {
        fscanf(f,"%lf %lf",&P[i].first,&P[i].second);
        bands.push_back(P[i].first);
    }
    sort(bands.begin(),bands.end());
    bands.resize(distance(bands.begin(),unique(bands.begin(),bands.end())));
    for(int i=0;i<bands.size()-1;i++)
    {
        double x1=bands[i],x2=bands[i+1];
        for(int j=1;j<=N;j++)
        {
            pair<double,double> P1=P[j],P2=P[j%N+1];
            if(P1>P2)swap(P1,P2);
            if(P1.first<=x1&&x2<=P2.first)
            {
                double A=P2.second-P1.second,B=P1.first-P2.first,C=1LL*P1.second*P2.first-1LL*P1.first*P2.second;
                double y1=(-C-A*x1)/B;
                double y2=(-C-A*x2)/B;
                V[i].push_back({{x1,y1},{x2,y2}});
            }
        }
        V[i].push_back({{-100,-100},{-100,-100}});
        sort(V[i].begin(),V[i].end(),cmp);
    }
    double xmin=bands[0],xmax=bands.back();
    for(int i=1;i<=M;i++)
    {
        double x,y;
        fscanf(f,"%lf%lf",&x,&y);
        if(x<xmin||x>xmax)continue;
        int ind,st=0,dr=bands.size()-2;
        while(st<dr)
        {
            int mid=(st+dr+1)/2;
            if(bands[mid]<=x&&x<=bands[mid+1]){st=mid;break;}
            else if(x<=bands[mid])dr=mid-1;
            else st=mid+1;
        }
        ind=st;
        st=0;dr=V[ind].size()-1;
        while(st<dr)
        {
            int mid=(st+dr+1)/2;
            if(det(V[ind][mid].first,V[ind][mid].second,{x,y})==0){st=1;break;}
            else if(det(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\n",rez);
    fclose(f);
    fclose(g);
    return 0;
}
/*


*/