Pagini recente » Cod sursa (job #1483312) | Cod sursa (job #1558331) | Cod sursa (job #1288392) | Cod sursa (job #965693) | Cod sursa (job #776683)
Cod sursa(job #776683)
#include <fstream>
#include <algorithm>
#include <utility>
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;
int result, onboard;
inline int intersect(const pair<int, int>& P, const pair<int, int>& p1, const pair<int, int> p2)
{
int64 a2 = (p1.y - p2.y), b2 = (p2.x - p1.x), c2 = (1LL * p1.x * p2.y - 1LL * p1.y * p2.x);
if (a2 * P.x + b2 * P.y + c2 == 0 && P.y >= min(p1.y, p2.y) && P.y <= max(p1.y, p2.y) && P.x >= min(p1.x, p2.x) && P.x <= max(p1.x, p2.x)) onboard = 1;
if (a2 == 0) return 0;
if (a2 < 0)
a2 *= -1, b2 *= -1, c2 *= -1;
if (P.y >= min(p1.y, p2.y) && P.y <= max(p1.y, p2.y))
return 1LL * P.x * a2 <= (-P.y) * b2 - c2;
else
return 0;
}
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;
A[N + 1] = A[1];
for (int i = 1; i <= M; ++i)
{
fin >> B.x >> B.y;
int nums = 0;
onboard = 0;
for (int j = 1; j <= N; ++j)
nums += intersect(B, A[j], A[j + 1]);
result += max(onboard, nums % 2);
}
fout << result << '\n';
fin.close();
fout.close();
}