Pagini recente » Cod sursa (job #1371744) | Cod sursa (job #1649138) | Cod sursa (job #917087) | Cod sursa (job #1274741) | Cod sursa (job #1139738)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
int N, M;
int banda, lowerpoints;
int sol, nrdrepte;
double ecm[801], ecn[801];
int D[801];
vector<pair<double, int> > V[801];
struct puncte
{
int x, y;
};
puncte A[801], B[801], punct;
struct dreapta
{
int a, b, c;
};
dreapta Ec[801];
bool cmp(puncte a, puncte b)
{
return (a.x < b.x || (a.x == b.x && a.y < b.y));
}
double gety(int now, double xnow)
{
return ecm[now] * xnow + ecn[now];
}
int onLine, curBucket;
bool check(int x0, int y0, int curLine) {
if (Ec[curLine].a * x0 + Ec[curLine].b * y0 + Ec[curLine].c == 0)
onLine = 1;
double lineY = (-Ec[curLine].c - Ec[curLine].a * x0) / Ec[curLine].b;
return y0 >= lineY;
}
int main()
{
fin >> N >> M;
for (int i = 1; i <= N; ++i)
{
fin >> A[i].x >> A[i].y;
B[i] = A[i];
}
A[N + 1] = A[1];
sort(B + 1, B + N + 1, cmp);
B[0].x = B[1].x + 1;
for (int i = 1; i <= N; ++i)
if (B[i - 1].x != B[i].x)
D[++nrdrepte] = B[i].x;
for (int i = 1; i <= N; ++i)
{
Ec[i].a = A[i + 1].y - A[i].y;
Ec[i].b = A[i].x - A[i + 1].x;
Ec[i].c = A[i + 1].x * A[i].y - A[i].x * A[i + 1].y;
ecm[i] = -1.0 * Ec[i].a / Ec[i].b;
ecn[i] = -1.0 * Ec[i].c / Ec[i].b;
}
for (int i = 1; i < nrdrepte; ++i)
{
for (int j = 1; j <= N; ++j)
{
if (A[j].x == A[j + 1].x) continue;
if (min(A[j].x, A[j + 1].x) <= D[i] && D[i + 1] <= max(A[j].x, A[j + 1].x))
{
double yb = gety(j, (D[i] + D[i + 1]) / 2.0);
V[i].push_back(make_pair(yb, j));
}
}
sort(V[i].begin(), V[i].end());
}
while (M)
{
fin >> punct.x >> punct.y;
if (punct.x < D[1] || punct.x > D[nrdrepte])
continue;
curBucket = onLine = 0;
for (int step = 10; step >= 0; --step)
if (curBucket + (1 << step) <= nrdrepte && D[curBucket + (1 << step)] < punct.x)
curBucket += (1 << step);
int j = 0;
for (int step = 10; step >= 0; --step)
if (j + (1 << step) <= V[curBucket].size() && check(punct.x, punct.y, V[curBucket][j + (1 << step) - 1].second))
j += (1 << step);
if (j % 2 == 1 || onLine == 1)
++sol;
--M;
}
fout << sol;
fin.close();
fout.close();
return 0;
}