Pagini recente » Cod sursa (job #224500) | Cod sursa (job #2900290) | Cod sursa (job #3277700) | Cod sursa (job #807346) | Cod sursa (job #990287)
Cod sursa(job #990287)
#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;
double CompactA[810], CompactC[810];
vector<int> Strip[810];
int OnEdge;
struct Comp
{
bool operator() (int Idx1, int Idx2)
{
return (CompactA[Idx1] * (Left + Right) + 2 * CompactC[Idx1] < CompactA[Idx2] * (Left + Right) + 2 * CompactC[Idx2]);
}
};
bool Check(int Index, pair<int, int> Point)
{
if(A[Index] * Point.X + B[Index] * Point.Y + C[Index] == 0) OnEdge = 1;
if(B[Index] >= 0) return A[Index] * Point.X + B[Index] * Point.Y + C[Index] >= 0;
else return A[Index] * Point.X + B[Index] * Point.Y + C[Index] <= 0;
}
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);
CompactA[i] = -1.0 * A[i] / B[i];
CompactC[i] = -1.0 * C[i] / B[i];
}
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 = 1024; Step; Step /= 2)
if(GoodStrip + Step <= X[0] && X[GoodStrip + Step] < P.X)
GoodStrip += Step;
for(int Step = 1024; 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;
}