Pagini recente » Cod sursa (job #618887) | Cod sursa (job #216529) | oji2008 | Cod sursa (job #1088903) | Cod sursa (job #990269)
Cod sursa(job #990269)
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define X first
#define Y second
pair<int, int> V[810], P;
int S[810], X[810], A[810], B[810], C[810], Ans, N, M, Left, Right;
vector<int> Strip[810];
int OnEdge;
struct Comp
{
bool operator() (int Idx1, int Idx2)
{
return ((-1.0 * A[Idx1] / B[Idx1]) * (Left + Right) - (2.0 * C[Idx1] / B[Idx1]) < (-1.0 * A[Idx2] / B[Idx2]) * (Left + Right) - (2.0 * C[Idx2] / B[Idx2]));
}
};
bool Check(int Index, pair<int, int> Point)
{
if(A[Index] * Point.X + B[Index] * Point.Y + C[Index] == 0) OnEdge = 1;
return Point.Y >= (-1.0 * A[Index] / B[Index]) * Point.X - (1.0 * (C[Index] / B[Index]));
}
int main()
{
freopen("poligon.in", "r", stdin);
freopen("poligon.out", "w", stdout);
scanf("%i %i", &N, &M);
for(int i = 1; i <= N; ++ i)
scanf("%i %i", &V[i].X, &V[i].Y);
V[N + 1] = V[1];
for(int i = 1; i <= N; ++ i)
S[i] = V[i].X;
sort(S + 1, S + N + 1);
X[++ X[0]] = S[1];
for(int i = 2; i <= N; ++ i)
if(S[i] != S[i - 1])
X[++ X[0]] = S[i];
for(int 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] = (V[i].Y * V[i + 1].X - V[i].X * V[i + 1].Y);
}
for(int i = 1; i <= X[0]; ++ i)
{
Left = X[i];
Right = X[i + 1];
for(int j = 1; j <= N; ++ j)
if(min(V[j].X, V[j + 1].X) <= X[i] && X[i] < max(V[j].X, V[j + 1].X))
Strip[i].push_back(j);
sort(Strip[i].begin(), Strip[i].end(), Comp());
}
for(int i = 1; i <= M; ++ i)
{
scanf("%i %i", &P.X, &P.Y);
if(!(X[1] <= P.X && P.X <= X[X[0]])) continue;
int GoodStrip = 0, CntUnder = 0;
OnEdge = 0;
for(int Step = 2048; Step; Step /= 2)
if(GoodStrip + Step <= X[0] && X[GoodStrip + Step] < P.X)
GoodStrip += Step;
for(int Step = 2048; Step; Step /= 2)
if(CntUnder + Step <= Strip[GoodStrip].size() && Check(Strip[GoodStrip][CntUnder + Step - 1], P))
CntUnder += Step;
if(OnEdge || CntUnder % 2 == 1) Ans ++;
}
printf("%i\n", Ans);
return 0;
}