Pagini recente » Cod sursa (job #2563777) | Cod sursa (job #2887636) | Cod sursa (job #3243160) | Cod sursa (job #623757) | Cod sursa (job #1588179)
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
#define NM 810
#define x first
#define y second
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
typedef pair<int, int> PI;
int N,M,ANS;
int i,j;
PI V[NM],Q;
int A[NM],B[NM],C[NM];
double Slope[NM],C2[NM];
int X[NM],NX;
vector<int> Strip[NM];
bool Online;
inline bool CMP (int a, int b)
{
return (Slope[a]*(X[i]+X[i+1])+2*C2[a]<Slope[b]*(X[i]+X[i+1])+2*C2[b]);
}
inline bool Check (int i, PI Q)
{
if (A[i]*Q.x+B[i]*Q.y+C[i]==0) Online=1;
return (Q.y>=Slope[i]*Q.x+C2[i]);
}
int main ()
{
f >> N >> M;
for (i=1; i<=N; i++)
{
f >> V[i].x >> V[i].y;
X[i]=V[i].x;
}
V[N+1]=V[1];
sort(X+1,X+N+1);
X[NX=1]=X[1];
for (i=2; i<=N; i++)
if (X[i]!=X[i-1])
X[++NX]=X[i];
X[NX+1]=0;
for (i=1; i<=N; i++)
{
A[i]=V[i+1].y-V[i].y;
B[i]=V[i].x-V[i+1].x;
C[i]=-(A[i]*V[i].x+B[i]*V[i].y);
Slope[i]=-1.0*A[i]/B[i];
C2[i]=-1.0*C[i]/B[i];
}
for (i=1; i<=NX; i++)
{
for (j=1; j<=N; j++)
if (X[i]>=min(V[j].x,V[j+1].x) && X[i]<max(V[j].x,V[j+1].x))
Strip[i].push_back(j);
sort(Strip[i].begin(),Strip[i].end(),CMP);
}
for (; M>=1; M--)
{
f >> Q.x >> Q.y;
if (Q.x<X[1] || Q.x>X[NX]) continue;
Online=0;
int step;
for (step=1024,i=0; step>0; step>>=1)
if (i+step<=NX && X[i+step]<Q.x)
i+=step;
for (step=1024,j=0; step>0; step>>=1)
if (j+step<=Strip[i].size() && Check(Strip[i][j+step-1],Q))
j+=step;
if (j%2==1 || Online==1)
ANS++;
}
g << ANS << '\n';
f.close();
g.close();
return 0;
}