Pagini recente » Cod sursa (job #796908) | Cod sursa (job #2196562) | Cod sursa (job #2290523) | Cod sursa (job #1064315) | Cod sursa (job #1197900)
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
#define NMAX 850
#define VMAX 60001
#define Dif 0.0000001
#define LL long long
pair < int , int > P[NMAX];
struct line
{
int a;
int b;
LL c;
}
Equation[NMAX];
vector < int > L[NMAX];
double OX_Equation[NMAX];
double OY_Equation[NMAX];
bool sel[VMAX];
int B[NMAX];
int now_B,N,M,sol;
int get(int X)
{
int Left,Right,Mid;
Left=0,Right=B[0]+1;
while (Right>Left+1)
{
Mid=(Left+Right)/2;
(B[Mid]<=X) ? Left=Mid : Right=Mid;
}
return Left;
}
double Y_get(int X,int Y)
{
return OY_Equation[X]*Y/2.0+OX_Equation[X];
}
bool cmp(int X,int Y)
{
int Mid;
double Y1,Y2;
Mid=B[now_B]+B[now_B+1];
Y1=Y_get(X,Mid);
Y2=Y_get(Y,Mid);
return Y2-Y1>Dif;
}
int solve()
{
int X,Y,nowB,Left,Right,Mid,cnt;
LL D;
scanf("%d%d",&X,&Y);
if (X<B[1] || X>B[B[0]]) return 0;
now_B=get(X);
if (now_B==B[0])
{
if (sel[Y]) return 1;
return 0;
}
Left=-1,Right=L[now_B].size();
while (Right>Left+1)
{
Mid=(Right+Left)/2;
cnt=L[now_B][Mid];
D=1LL*Equation[cnt].a*X + 1LL*Equation[cnt].b*Y + Equation[cnt].c;
if (!D) return 1;
(D>0) ? Left=Mid : Right=Mid;
}
++Left;
if (Left&1)
return 1;
return 0;
}
void lines_select()
{
int i,up_lim,down_lim,j;
for (i=1;i<=N;++i)
if (max(P[i].first,P[i+1].first)==B[B[0]])
{
if (min(P[i].first,P[i+1].first)==B[B[0]])
{
up_lim=max(P[i].second,P[i+1].second);
down_lim=min(P[i].second,P[i+1].second);
for (j=down_lim;j<=up_lim;++j)
sel[j]=true;
}
else (P[i].first==B[B[0]]) ? sel[P[i].second]=true : sel[P[i+1].second]=true;
}
}
void Read()
{
int i;
scanf("%d%d",&N,&M);
for (i=1;i<=N;++i)
{
scanf("%d%d",&P[i].first,&P[i].second);
B[i]=P[i].first;
}
P[N+1]=P[1];
sort(B+1,B+N+1);
B[0]=1;
for (i=2;i<=N;++i)
{
if (B[i]==B[B[0]]) continue;
B[++B[0]]=B[i];
}
}
void build_lines()
{
int i,j;
for (i=1;i<=B[0];++i)
{
for (j=1;j<=N;++j)
{
if (min(P[j].first,P[j+1].first)>B[i]) continue;
if (B[i]>=max(P[j].first,P[j+1].first)) continue;
L[i].push_back(j);
}
now_B=i;
sort(L[i].begin(),L[i].end(),cmp);
}
}
void build_Equations()
{
int i,sgn1,sgn2;
for (i=1;i<=N;++i)
{
(P[i].first<P[i+1].first) ? sgn1=1: sgn1=-1;
sgn2=-sgn1;
Equation[i].a=sgn1*P[i].second + sgn2*P[i+1].second;
Equation[i].b=sgn1*P[i+1].first + sgn2*P[i].first;
Equation[i].c=1LL*sgn1*P[i].first*P[i+1].second + 1LL*sgn2*P[i].second*P[i+1].first;
OY_Equation[i]=(-1.0*Equation[i].a)/(1.0*Equation[i].b);
OX_Equation[i]=(-1.0*Equation[i].c)/(1.0*Equation[i].b);
}
}
int main()
{
freopen("poligon.in","r",stdin);
freopen("poligon.out","w",stdout);
Read();
build_Equations();
build_lines();
lines_select();
while (M--)
sol+=solve();
printf("%d\n",sol);
return 0;
}