Cod sursa(job #1950925)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 3 aprilie 2017 12:42:27
Problema Poligon Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
FILE *f=fopen("poligon.in","r");
FILE *g=fopen("poligon.out","w");
vector<int> V[60005];
struct punct{
    int x,y;
    punct()
    {
        x=y=0;
    }
    punct(int a,int b)
    {
        x=a;
        y=b;
    }
};
bool operator < (const punct &a,const punct &b)
{
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
struct dreapta
{
    int a,b;
    long long c;
    dreapta()
    {
        ;
    }
    dreapta(punct A,punct B)
    {
        a=B.y-A.y;
        b=A.x-B.x;
        c=1LL*B.x*A.y-1LL*A.x*B.y;
    }
};
punct P[60005];
dreapta tmp;
set<punct> S;
int N,M;
int main()
{
    fscanf(f,"%d %d",&N,&M);
    for(int i=1;i<=N;i++)
    {
        fscanf(f,"%d%d",&P[i].x,&P[i].y);
    }
    for(int i=1;i<=N;i++)
    {
        tmp=dreapta(P[i],P[(i==N ? 1:i+1)]);
        if(tmp.a==0) {S.insert({P[i].y,max(P[i].x,P[(i==N ? 1:i+1)].x)});V[P[i].y].push_back(min(P[i].x,P[(i==N ? 1:i+1)].x));V[P[i].y].push_back(max(P[i].x,P[(i==N ? 1:i+1)].x));continue;}
        int st=min(P[i].y,P[(i==N ? 1:i+1)].y),dr=max(P[i].y,P[(i==N ? 1:i+1)].y);
        for(int y=st+1;y<=dr;y++)
        {
            V[y].push_back(-(1LL*tmp.b*y+tmp.c)/tmp.a);
            if(-(1LL*tmp.b*y+tmp.c)%tmp.a==0)
            S.insert({y,-(1LL*tmp.b*y+tmp.c)/tmp.a});
        }
    }
    for(int y=0;y<=60000;y++) sort(V[y].begin(),V[y].end());
    int nr=0;
    for(int i=1;i<=M;i++)
    {
        punct tmp;
        fscanf(f,"%d %d",&tmp.x,&tmp.y);
        int a=(lower_bound(V[tmp.y].begin(),V[tmp.y].end(),tmp.x)-V[tmp.y].begin());
        if(a%2==1)nr++;
        else if(S.find(tmp)!=S.end()) nr++;
    }
    fprintf(g,"%d",nr);
    fclose(f);
    fclose(g);
    return 0;
}