Pagini recente » Cod sursa (job #1088801) | Cod sursa (job #1182061) | Cod sursa (job #869407) | Cod sursa (job #546511) | Cod sursa (job #776809)
Cod sursa(job #776809)
#include <cmath>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const double eps = 0.0001;
#define x first
#define y second
int N, aN, M;
pair<int, int> A[802];
int B[802];
int result, onboard;
vector<int> V[802];
int wA[802], wB[802], wC[802];
int xboth1, xboth2;
inline double gety(const int& what, const int& xnow)
{
return 1.0 * (1.0 * (-wA[what]) * xnow - wC[what]) / wB[what];
}
class sortnow
{
public: inline bool operator () (const int& i1, const int& i2)
{
return (gety(i1, xboth1) + gety(i1, xboth2) < gety(i2, xboth1) + gety(i2, xboth2));
}
};
inline bool intersect(const int& P, const pair<int, int>& p1, const pair<int, int>& p2)
{
return (P >= min(p1.x, p2.x) && P < max(p1.x, p2.x));
}
inline bool higher(const pair<int, int>& P, const int& what)
{
if (1LL * wA[what] * P.x + 1LL * wB[what] * P.y + wC[what] == 0) onboard = 1;
double ypoint = 1.0 * (1LL * (-P.x) * wA[what] - wC[what]) / wB[what];
return (P.y >= ypoint);
}
int main()
{
ifstream fin("poligon.in");
ofstream fout("poligon.out");
fin >> N >> M;
for (int i = 1; i <= N; ++i)
{
fin >> A[i].x >> A[i].y;
B[i] = A[i].x;
}
A[N + 1] = A[1];
for (int i = 1; i <= N; ++i)
{
wA[i] = (A[i].y - A[i + 1].y);
wB[i] = (A[i + 1].x - A[i].x);
wC[i] = (A[i].x * A[i + 1].y - A[i].y * A[i + 1].x);
}
sort(B + 1, B + N + 1);
for (int i = 1; i <= N; ++i)
{
B[++aN] = B[i];
while (i < N && B[i] == B[i + 1])
++i;
}
for (int i = 1; i <= aN; ++i) // duc din punctul B[i] o verticala
{
for (int j = 1; j <= N; ++j)
if (intersect(B[i], A[j], A[j + 1]))
V[i].push_back(j);
xboth1 = B[i], xboth2 = B[i + 1];
sort(V[i].begin(), V[i].end(), sortnow());
}
pair<int, int> now;
for (int i = 1; i <= M; ++i)
{
fin >> now.x >> now.y;
if (now.x < B[1] || now.x > B[aN]) continue;
onboard = 0;
int step = 1 << 9, gonow, upped;
for (gonow = 0; step; step >>= 1)
if (gonow + step <= aN && B[gonow + step] <= now.x)
gonow += step;
step = 1;
for (; step <= V[gonow].size(); step <<= 1);
upped = 0;
for (; step; step >>= 1)
if (upped + step <= V[gonow].size() && higher(now, V[gonow][upped + step - 1]))
upped += step;
result += max(upped % 2, onboard);
}
fout << result << '\n';
fin.close();
fout.close();
}