Pagini recente » Cod sursa (job #2109719) | Cod sursa (job #2870403) | Cod sursa (job #2643148) | Cod sursa (job #984811) | Cod sursa (job #1953917)
#include <cstdio>
#include <vector>
#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;
}
};
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;
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) 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);
}
}
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);
nr+=((lower_bound(V[tmp.y].begin(),V[tmp.y].end(),tmp.x)-V[tmp.y].begin())%2==1||(upper_bound(V[tmp.y].begin(),V[tmp.y].end(),tmp.x)-V[tmp.y].begin())%2==1);
}
fprintf(g,"%d",nr);
fclose(f);
fclose(g);
return 0;
}