Pagini recente » Cod sursa (job #2743471) | Cod sursa (job #2088759) | Cod sursa (job #1582189) | Cod sursa (job #195821) | Cod sursa (job #788680)
Cod sursa(job #788680)
#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];
int X[NM],NX;
vector<int> Strip[NM];
bool Online;
inline bool CMP (int a, int b)
{
double y1,y2;
y1=( (1.0*C[a]-A[a]*X[i])/B[a]+(1.0*C[a]-A[a]*X[i+1])/B[a] )/2;
y2=( (1.0*C[b]-A[b]*X[i])/B[b]+(1.0*C[b]-A[b]*X[i+1])/B[b] )/2;
return y1<y2;
}
inline int SearchStrip (int x)
{
int P=1,M,U=NX,ANS=NX;
while (P<=U)
{
M=(P+U)/2;
if (x>=X[M])
{
ANS=M;
U=M-1;
}
else
P=M+1;
}
return ANS;
}
inline int Sign (const PI& P1, const PI& P2, const PI& P3)
{
int S=P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y;
if (S==0) return 0;
return (S<0?-1:1);
}
inline int SearchLine (const PI& Q)
{
int P=0,U=Strip[i].size()-1,M,ANS=0;
while (P<=U)
{
M=(P+U)/2;
if (Sign(V[Strip[i][M]],V[Strip[i][M]+1],Q)>=0)
{
if (Sign(V[Strip[i][M]],V[Strip[i][M]+1],Q)==0) Online=1;
ANS=M;
P=M+1;
}
else
U=M-1;
}
return ANS;
}
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];
X[0]=-1;
for (i=2; i<=N; i++)
if (X[i]!=X[i-1])
X[++NX]=X[i];
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;
}
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;
i=SearchStrip(Q.x);
j=SearchLine(Q);
if (j%2==1 || Online==1)
ANS++;
}
g << ANS << '\n';
f.close();
g.close();
return 0;
}