Pagini recente » Cod sursa (job #81884) | Cod sursa (job #1723997) | Cod sursa (job #1542741) | Cod sursa (job #1357533) | Cod sursa (job #776664)
Cod sursa(job #776664)
#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;
inline bool intersect(const pair<int, int>& P, const pair<int, int>& p1, const pair<int, int> p2)
{
int64 b1 = 1, c1 = -P.y;
int64 a2 = (p1.y - p2.y), b2 = (p2.x - p1.x), c2 = (1LL * p1.x * p2.y - 1LL * p1.y * p2.x);
if (a2 == 0)
return (P.y == p1.y && max(p1.x, p2.x) >= P.x);
double px = 1.0 * (c1 * b2 - c2 * b1) / (a2 * b1);
if (P.y >= min(p1.y, p2.y) && P.y <= max(p1.y, p2.y))
return P.x <= px;
else
return false;
}
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;
for (int j = 1; j <= N; ++j)
if (!(A[j].y == A[j + 1].y && A[j + 1].y == A[j + 2].y) && intersect(B, A[j], A[j + 1]))
++nums;
result += nums % 2;
}
fout << result << '\n';
fin.close();
fout.close();
}