Pagini recente » Cod sursa (job #797928) | Cod sursa (job #715532) | Cod sursa (job #960492) | Cod sursa (job #3143124) | Cod sursa (job #1211763)
#include <iostream>
#include <fstream>
#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;
int N, M, Sol, CutEdges;
struct point {
int x, y;
}polygon[MAXN], crime[MAXM];
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
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
/**if we enter this IF statement
we surely do NOT have a horizontal edge**/
double m = (double)(polygon[j].x - polygon[j + 1].x) / (polygon[j].y - polygon[j + 1].y);// slope^(-1)
double x = (double)(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;
}