Pagini recente » Cod sursa (job #1252716) | Cod sursa (job #3128897) | Cod sursa (job #2081485) | Cod sursa (job #660557) | Cod sursa (job #1209899)
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
//brute-force O(N*M) using areas
ifstream fin("poligon.in");
ofstream fout("poligon.out");
const int MAXN = 805;
const int MAXM = 60005;
int N, M, Sol;
struct punct {
int x, y;
}polygon[MAXN], crime[MAXM];
long double Area, NewArea;
double Det(punct A, punct B, punct C) {
double r = A.x * B.y + B.x * C.y + C.x * A.y - C.x * B.y - A.x * C.y - B.x * A.y;
return abs(r);
}
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() {
//first calculate the area of the polygon
for (int i = 0; i < N; ++i)
Area += polygon[i].x * polygon[i + 1].y - polygon[i + 1].x * polygon[i].y;
Area = abs(0.5 * Area);
//for each point we see if it is inside the polygon
//by calculating its area and comparing it to the
//original area of the polygon
for (int i = 0; i < M; ++i) {
NewArea = 0.0;
for (int j = 0; j < N; ++j)
NewArea += Det(crime[i], polygon[j], polygon[j + 1]);
NewArea = abs(0.5 * NewArea);
if (NewArea <= Area)
++Sol;
}
}
void Write() {
fout << Sol << '\n';
}
int main() {
Read();
Solve();
Write();
fin.close();
fout.close();
return 0;
}