Pagini recente » Cod sursa (job #1751091) | Cod sursa (job #403468) | Cod sursa (job #373359) | Cod sursa (job #535866) | Cod sursa (job #342225)
Cod sursa(job #342225)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cmath>
#include <set>
using namespace std;
const int MAXN = 810;
const int INF = 100000;
const double eps = 0.00000001;
#define MP make_pair
#define ff first
#define ss second
int N, M, L, Sol;
int A[MAXN], B[MAXN], X[MAXN];
vector <int> V[MAXN];
double medx;
set <pair <int, pair <int, int> > > S;
inline double getY(int i, double x)
{
assert(A[i] != A[i+1]);
double m = (double) (B[i+1] - B[i]) / (A[i+1] - A[i]);
double n = B[i] - m * A[i];
return m*x + n;
}
inline int cmp(int i, int j)
{
return getY(i, medx) < getY(j, medx);
}
int isInside(int i, int x, int y)
{
int front = 0, middle, back = V[i].size() - 1, res = -1;
while (front <= back)
{
middle = (front + back) / 2;
if (getY(V[i][middle], x) <= y)
{
res = middle;
front = middle + 1;
}
else back = middle - 1;
}
if (res >= 0 && fabs(getY(V[i][res], x) - y) < eps) return 1;
if (res+1 < (int) V[i].size() && fabs(getY(V[i][res+1], x) - y) < eps) return 1;
return !(res&1);
}
int main()
{
ifstream fin("poligon.in");
ofstream fout("poligon.out");
fin >> N >> M;
for (int i = 1; i <= N; ++i)
{
fin >> A[i] >> B[i];
X[i] = A[i];
}
A[N+1] = A[1], B[N+1] = B[1];
X[0] = -1;
sort(X, X+N+1);
L = unique(X, X+N+1) - X;
X[L] = INF;
for (int i = 1; i <= N; ++i)
for (int j = 0; j < L; ++j)
{
if ((A[i] <= X[j] && X[j+1] <= A[i+1]) || (A[i+1] <= X[j] && X[j+1] <= A[i])) V[j].push_back(i);
if (A[i] == A[i+1] && A[i] == X[j]) S.insert(MP(X[j], MP( min(B[i], B[i+1]), max(B[i], B[i+1]))));
}
for (int i = 0; i < L; ++i)
{
medx = (X[i] + X[i+1]) / 2.0;
sort(V[i].begin(), V[i].end(), cmp);
}
for (int i = 1; i <= M; ++i)
{
int x, y;
fin >> x >> y;
int j = upper_bound(X, X+L, x) - 1 - X;
if (X[j] != x) Sol += isInside(j, x, y);
else {
set < pair <int, pair <int, int> > > :: iterator it = --S.upper_bound(MP(x, MP(y, INF)));
Sol += it->ss.ff <= y && y <= it->ss.ss;
}
}
fout << Sol << endl;
return 0;
}