Cod sursa(job #2060494)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 8 noiembrie 2017 12:29:06
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
FILE *f=fopen("poligon.in","r");
FILE *g=fopen("poligon.out","w");
pair<int,int> P[805];
vector<int> bands;
vector<pair<pair<int,int>,pair<int,int> > > V[805];
///belit pt puncte care se afla pe o latura verticala
///fix later
int N,M,rez;
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;
}
long long det(pair<long long,long long> a,pair<long long,long long> b,pair<long long,long long> 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,"%d %d",&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++)
    {
        int 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&&x2<=P2.first)
            {
                long long A=P2.second-P1.second,B=P1.first-P2.first,C=1LL*P1.second*P2.first-1LL*P1.first*P2.second;
                int y1=(-C-A*x1)/B;
                int 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);
    }
    int xmin=bands[0],xmax=bands.back();
    bands.pop_back();
    for(int i=1;i<=M;i++)
    {
        int x,y;
        fscanf(f,"%d%d",&x,&y);
        if(x<xmin||x>xmax)continue;
        int ind,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;
        }
        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);
    }
    fprintf(g,"%d\n",rez);
    fclose(f);
    fclose(g);
    return 0;
}
/*
14 8
22 21
68 10
69 34
55 42
52 30
47 37
45 24
37 31
28 44
12 36
25 30
12 26
26 29
17 20
31 28
8 40
3 16
25 7
52 21
41 37
65 25
71 13

*/