Pagini recente » Cod sursa (job #862676) | Cod sursa (job #2570670) | Cod sursa (job #1517395) | Istoria paginii runda/conc1/clasament | Cod sursa (job #776659)
Cod sursa(job #776659)
#include <fstream>
#include <algorithm>
#include <utility>
using namespace std;
const double eps = 0.00001;
#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)
{
int b1 = 1, c1 = -P.y;
int a2 = (p1.y - p2.y), b2 = (p2.x - p1.x), c2 = (p1.x * p2.y - 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);
double py = -1.0 * c1 / b1;
if (py >= min(p1.y, p2.y) && py <= 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 (intersect(B, A[j], A[j + 1]))
++nums;
result += nums % 2;
}
fout << result << '\n';
fin.close();
fout.close();
}