Pagini recente » Cod sursa (job #2536749) | Cod sursa (job #2095123) | Cod sursa (job #2877183) | Cod sursa (job #1041457) | Cod sursa (job #1098534)
#include <fstream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
template<const int N>
class Poligon{
struct Point{
int x, y;
inline bool operator==(const Point& P) const {
return x == P.x && y == P.y;
}
};
struct Segm{
Point A, B;
Segm() : A(), B() {};
Segm(Point _A, Point _B){
if (_A.x > _B.x){
A = _B;
B = _A;
} else {
A = _A;
B = _B;
}
}
inline bool operator<(const Segm& S) const {
if (B.x < S.A.x)
return false;
if (B == S.B)
return A.y < S.A.y;
if (A == S.A)
return B.y < S.B.y;
return getSide(S.A.x, S.A.y) < 0;
}
long long getSide(long long x, long long y) const {
return (y - A.y) * ((int)B.x - A.x) - (x - A.x) * ((int)B.y - A.y);
}
};
Point P[N + 1];
Segm S[N];
int X[N], nrP, nrFile, startStep;
vector<int> file[N];
int binSrcX(int x){
int ans = 0;
for (int step = startStep, aux = startStep ; step ; step >>= 1, aux = ans ^ step)
if (aux < nrFile && X[aux] <= x)
ans = aux;
return ans;
}
bool isInside(vector<int>& v, int x, int y){
if (v.empty() || S[ v[0] ].getSide(x, y) < 0)
return false;
unsigned int ans = 0;
for (unsigned int step = startStep, aux = startStep ; step ; step >>= 1, aux = ans ^ step)
if ( aux < v.size() && S[ v[aux] ].getSide(x, y) >= 0 )
ans = aux;
return (ans & 1) == 0 || S[ v[ans] ].getSide(x, y ) == 0;
}
void sortare(){
for (int i = 0 ; i < nrP ; i++)
for (int j = i + 1 ; j < nrP ; j++)
if ( S[j] < S[i] )
swap(S[i], S[j]);
}
public:
Poligon(){
nrP = 0;
}
void add(int x, int y){
P[nrP].x = x;
P[nrP].y = y;
nrP++;
}
void preprocesare(){
///DETERMINE STEP SIZE
startStep = 1;
while ( (startStep << 1) <= nrP )
startStep <<= 1;
///INDEX BY X
for (int i = 0 ; i < nrP ; i++)
X[i] = P[i].x;
sort(X, X + nrP);
nrFile = 1;
for (int i = 1 ; i < nrP ; i++)
if (X[i] != X[i - 1])
X[nrFile++] = X[i];
///CREATE SEGMENTS
int st, dr;
P[nrP] = P[0];
for (int i = 0 ; i < nrP ; i++)
S[i] = Segm(P[i], P[i + 1]);
sortare();
///CREATE FILES
for (int i = 0 ; i < nrP ; i++){
st = binSrcX(S[i].A.x);
dr = binSrcX(S[i].B.x);
for (int j = st ; j < dr ; j++)
file[j].push_back(i);
}
}
bool query(int x, int y){
int P = binSrcX(x);
if (isInside( file[P], x, y ))
return true;
if (P && X[P] == x)
return isInside( file[P - 1], x, y );
return false;
}
};
Poligon<800> P;
ifstream in("poligon.in");
ofstream out("poligon.out");
int main(){
int n, nrQ, x, y;
in >> n >> nrQ;
for (int i = 1 ; i <= n ; i++){
in >> x >> y;
P.add(x, y);
}
P.preprocesare();
int ans = 0;
while (nrQ--){
in >> x >> y;
ans += P.query(x, y);
}
out << ans << "\n";
return 0;
}