Pagini recente » Cod sursa (job #1951549) | Cod sursa (job #2906714) | Cod sursa (job #2928068) | Cod sursa (job #2586768) | Cod sursa (job #1211624)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
const int MAXN = 809;
const int MAXM = 60009;
int N, M, Solution;
double SegmentMiddle[MAXN];//the middle of each segment
vector< vector<int> > Strips;
struct Point {
double x, y;
int indx;
//indx = a pointer to the position of a point in the original
//polygon order after it has been sorted by the x-coordinates, and vice-versa
}polygon[MAXN], crime[MAXM], aux[MAXM];
//polygon[] keeps the points on the polygon in their original order
//aux[] keeps the points sorted by the x-coordinates
//crime[] keeps the location of the crimes
struct cmp1 {
bool operator() (const Point &A, const Point &B) const {
return A.x < B.x;
}
};
struct cmp2 {
bool operator() (const int &A, const int &B) const {
return SegmentMiddle[A] < SegmentMiddle[B];
}
};
inline double Det(Point A, Point B, Point C) {
if (B.x > C.x) swap(B, C);
return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}
void Read() {
fin >> N >> M;
//read the polygon
for (int i = 0; i < N; ++i) {
fin >> polygon[i].x >> polygon[i].y;
aux[i] = polygon[i];
aux[i].indx = i;
}
polygon[N] = polygon[0];
aux[N] = polygon[0];
aux[N].indx = 0;
/**I've inserted this axis as an invariant for the second
binary search to work, even when the point has no edges beneath**/
polygon[N + 1].x = 0, polygon[N + 1].y = -1;
polygon[N + 2].x = 60001, polygon[N + 2].y = -1;
//now an upper-bound
polygon[N + 3].x = 0, polygon[N + 3].y = 60001;
polygon[N + 4].x = 60001, polygon[N + 4].y = 60001;
//read the crime points
for (int i = 0; i < M; ++i)
fin >> crime[i].x >> crime[i].y;
}
int BinarySearchStrip(int i) {
Point P = crime[i];
int Hi = N - 1, Lo = 0, Middle;
while (Hi - Lo > 1) {
Middle = (Hi + Lo) >> 1;
//cerr << '\n' << aux[ Middle ].x << '\n';
if (aux[ Middle ].x > P.x)
Hi = Middle;
else
Lo = Middle;
}
return Lo;
}
int BinarySearchPosition(Point P, int Strip) {
int Hi = Strips[Strip].size() - 1, Lo = 0, Middle;
while (Hi - Lo > 1) {
Middle = (Hi + Lo) >> 1;
//cerr << "middle=" << Middle << '\n';
if (Det(P, polygon[ Strips[Strip][Middle] ], polygon[ Strips[Strip][Middle] + 1 ]) > 0) {
Lo = Middle;
}else
if (Det(P, polygon[ Strips[Strip][Middle] ], polygon[ Strips[Strip][Middle] + 1 ]) < 0) {
Hi = Middle;
}else {
return 0;
}
//cerr << "Hi=" << Hi << " Lo=" << Lo << '\n';
}
return Lo;
}
void Solve() {
Strips.resize(MAXN);
//sort the points by the x-coordinate
sort(aux, aux + N, cmp1());
//mark where each point has moved to from the original index
for (int i = 0; i < N; ++i)
polygon[ aux[i].indx ].indx = i;
polygon[N].indx = polygon[0].indx;
//take each edge separately and insert it in the strips it passes through
for (int i = 0; i < N; ++i) {
Strips[i].push_back(N + 1);
Strips[i].push_back(N + 3);
for (int j = 0; j < N; ++j)
if (min(polygon[j].x, polygon[j + 1].x) <= aux[i].x
&& aux[i].x < max(polygon[j].x, polygon[j + 1].x))
Strips[i].push_back(j);
/*if (polygon[i].x == polygon[i + 1].x) continue;//vertical*/
}
//calculate each segments' middle
for (int i = 0; i <= N + 3; ++i)
SegmentMiddle[i] = (polygon[i].y + polygon[i + 1].y) / 2;
//sort the edges in each strip by their middle
for (int i = 0; i < N; ++i)
sort(Strips[i].begin(), Strips[i].end(), cmp2());
/*for (int i = 0; i < N; ++i) {
cerr << "Strip number " << i << ": ";
for (size_t j = 0; j < Strips[i].size(); ++j) {
cerr << Strips[i][j] << ' ';
}cerr << '\n';
}*/
for (int i = 0; i < M; ++i) {
if ((aux[N - 1].x <= crime[i].x) || (crime[i].x <= aux[0].x)) continue;
int Strip = BinarySearchStrip(i);//which band the point is in
//cerr << "Point #" << i << " is on Strip #" << Strip << '\n';
int poz = BinarySearchPosition(crime[i], Strip);
//cerr << "poz = " << poz << '\n';
//cerr << '\n';
Solution += poz % 2;
}
}
void Write() {
fout << Solution << '\n';
}
int main() {
Read();
Solve();
Write();
fin.close();
fout.close();
return 0;
}