Pagini recente » Cod sursa (job #727759) | Cod sursa (job #1042793) | Cod sursa (job #2553430) | Cod sursa (job #1471413) | Cod sursa (job #776723)
Cod sursa(job #776723)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const double eps = 0.001;
typedef long long int64;
#define x first
#define y second
int N, M;
pair<int, int> A[802];
pair<int, int> B[802];
int result, onboard;
vector<int> V[802], W[802];
class sortnow
{
public: inline bool operator () (const int& i1, const int& i2)
{
return A[i1].y + A[i1 + 1].y < A[i2].y + A[i2 + 1].y;
}
};
inline bool intersect(const pair<int, int>& P, const pair<int, int>& p1, const pair<int, int>& p2)
{
return (P.x >= min(p1.x, p2.x) && P.x < max(p1.x, p2.x));
}
inline bool intersect2(const pair<int, int>& P, const pair<int, int>& p1, const pair<int, int>& p2)
{
return (p1.x != p2.x && P.x >= min(p1.x, p2.x) && P.x <= max(p1.x, p2.x));
}
inline bool higher(const pair<int, int>& P, int what)
{
int a = (A[what].y - A[what + 1].y), b = (A[what + 1].x - A[what].x), c = (A[what].x * A[what + 1].y - A[what].y * A[what + 1].x);
if (1LL * a * P.x + 1LL * b * P.y + c == 0) onboard = 1;
double ypoint = 1.0 * (1LL * (-P.x) * a - c) / b;
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];
}
A[N + 1] = A[1];
sort(B + 1, B + N + 1);
for (int i = 1; i <= N; ++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);
if (intersect2(B[i], A[j], A[j + 1]))
W[i].push_back(j);
}
sort(V[i].begin(), V[i].end(), sortnow());
sort(W[i].begin(), W[i].end(), sortnow());
}
pair<int, int> now;
for (int i = 1; i <= M; ++i)
{
fin >> now.x >> now.y;
onboard = 0;
int step = 1 << 9, gonow, upped;
for (gonow = 0; step; step >>= 1)
if (gonow + step <= N && B[gonow + step].x <= now.x)
gonow += step;
if (now.x == B[gonow].x)
{
step = 1 << 9;
for (upped = 0; step; step >>= 1)
if (upped + step <= W[gonow].size() && higher(now, W[gonow][upped + step - 1]))
upped += step;
result += max(onboard, upped % 2);
}
else
{
step = 1 << 9;
for (upped = 0; step; step >>= 1)
if (upped + step <= V[gonow].size() && higher(now, V[gonow][upped + step - 1]))
upped += step;
result += max(onboard, upped % 2);
}
}
fout << result << '\n';
fin.close();
fout.close();
}