Pagini recente » Cod sursa (job #2660052) | Cod sursa (job #1999383) | Cod sursa (job #2682998) | Cod sursa (job #197148) | Cod sursa (job #1211762)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
//O(N*M) using a ray
ifstream fin("poligon.in");
ofstream fout("poligon.out");
const int MAXN = 805;
const int MAXM = 60005;
const int INF = 0x3f3f3f3f;
int N, M, Sol, CutEdges;
struct point {
double x, y;
}polygon[MAXN], crime[MAXM];
inline double slope(point A, point B) {
if (A.x - B.x == 0)
return INF;
return (A.y - B.y) / (A.x - B.x);
}
void Read() {
fin >> N >> M;
for (int i = 0; i < N; ++i)
fin >> polygon[i].x >> polygon[i].y;
polygon[N] = polygon[0];
for (int i = 0; i < M; ++i)
fin >> crime[i].x >> crime[i].y;
}
void Solve() {
for (int i = 0; i < M; ++i) {
//take each point and draw a horizontal ray to the right
point P = crime[i];
//and see how many edges it cuts
double m;
CutEdges = 0;
for (int j = 0; j < N; ++j) {
//first, check if the ray passes through this edge, either on the left or on the right
if ( ((polygon[j].y < P.y) and (P.y < polygon[j + 1].y))
|| ((polygon[j + 1].y < P.y) and (P.y < polygon[j].y)) ) {
//now check if the intersection point
//is on the right semi-plane of the x-coordinate
m = slope(polygon[j], polygon[j + 1]);
double x = (P.y - polygon[j].y) / m + polygon[j].x;
if (P.x < x)
++CutEdges;
}
}
Sol += CutEdges % 2;
}
}
void Write() {
fout << Sol << '\n';
}
int main() {
Read();
Solve();
Write();
fin.close();
fout.close();
return 0;
}