Pagini recente » Cod sursa (job #777855) | Cod sursa (job #1167281) | Cod sursa (job #2906537) | Cod sursa (job #2174167) | Cod sursa (job #868756)
Cod sursa(job #868756)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 805;
const int M = 60005;
struct Punct{
int x, y;
Punct(){
x = y = 0;
}
Punct(int _x, int _y){
x = _x;
y = _y;
}
inline bool operator<(const Punct& P) const{
return x < P.x;
}
};
struct Dreapta{
int a, b, c;
double ord;
Dreapta(){
a = b = c = 0;
}
Dreapta(Punct A, Punct B, int x){
a = A.y - B.y;
b = B.x - A.x;
c = A.x * B.y - A.y * B.x;
if (b < 0){
a = -a;
b = -b;
c = -c;
}
ord = -(double)(a * x + c) / b;
}
int operator[](Punct P){
return a * P.x + b * P.y + c;
}
inline bool operator<(const Dreapta& D) const {
return ord < D.ord;
}
};
class Fasie{
Dreapta a[N];
int n, st, dr;
public:
void init(int x, int y){
n = 0;
st = x;
dr = y;
}
void insert(Punct X, Punct Y){
a[++n] = Dreapta(X, Y, st);
}
void prepare(){
sort(a + 1, a + n + 1);
}
bool inside(Punct P){
int val = -1;
for (int step = 1 << 9 ; step ; step >>= 1)
if (val + step <= n && a[val + step][P] >= 0)
val += step;
if (val && a[val][P] == 0)
return true;
return val & 1;
}
};
class Vertical{
vector<Punct> a[M];
public:
void insert(int x, int y1, int y2){
if (y1 > y2)
swap(y1, y2);
a[x].push_back(Punct(y1, y2));
}
void prepare(){
for (int i = 0 ; i < M ; i++)
if (!a[i].empty())
sort(a[i].begin(), a[i].end());
}
bool inside(Punct P){
vector<Punct>& v = a[P.x];
if (v.empty())
return false;
int val = 0;
for (int step = 1 << 9 ; step ; step >>= 1)
if (val + step < v.size() && v[val + step].x <= P.y)
val += step;
return v[val].x <= P.y && P.y <= v[val].y;
}
};
Fasie fasie[N];
Vertical V;
Punct P[N];
int X[N], n;
ifstream in("poligon.in");
ofstream out("poligon.out");
void cleanup(int X[], int n){
sort(X + 1, X + n + 1);
X[0] = 1;
for (int i = 2 ; i <= n ; i++)
if (X[i] != X[i - 1])
X[++X[0]] = X[i];
}
int bsearch(int v[], int x){
int val = 0;
for (int step = 1 << 9 ; step ; step >>= 1)
if (val + step <= v[0] && v[val + step] <= x)
val += step;
return val;
}
void compute(Fasie& F, int st, int dr){
F.init(st, dr);
for (int i = 1 ; i <= n ; i++)
if (min(P[i].x, P[i + 1].x) <= st && dr <= max(P[i].x, P[i + 1].x))
F.insert(P[i], P[i + 1]);
F.prepare();
}
int main(){
Punct p;
int m;
in >> n >> m;
for (int i = 1 ; i <= n ; i++){
in >> P[i].x >> P[i].y;
X[i] = P[i].x;
}
P[n + 1] = P[1];
cleanup(X, n);
for (int i = 1 ; i < X[0] ; i++)
compute(fasie[i], X[i], X[i + 1]);
for (int i = 1 ; i <= n ; i++)
if (P[i].x == P[i + 1].x)
V.insert(P[i].x, P[i].y, P[i + 1].y);
V.prepare();
int ans = 0;
while (m--){
in >> p.x >> p.y;
ans += (V.inside(p) || fasie[bsearch(X, p.x)].inside(p));
}
out << ans << "\n";
return 0;
}