Pagini recente » Cod sursa (job #910947) | Cod sursa (job #1837485) | Cod sursa (job #1779766) | Cod sursa (job #676569) | Cod sursa (job #1736838)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
#define point pair<int, int>
#define pointd pair<double, double>
#define x first
#define y second
const int NMAX = 803;//nr vf-uri poligon
const int MMAX = 60009; //nr puncte
const int INF = 60009;
int n; int m;
point pol[NMAX];
point v[MMAX];
struct Segment {
double a; double b; double c;
pointd middle;
pointd p1;
pointd p2;
Segment(point _p1, point _p2) {
p1 = _p1;
p2 = _p2;
a = p1.y - p2.y;
b = p2.x - p1.x;
c = p1.x * p2.y - p1.y * p2.x;
middle = pointd( (p1.x + p2.x) * 0.5, (p1.y + p2.y) * 0.5);
}
bool operator<(Segment s) const {
return middle.y < s.middle.y; //segmentele nu se intersecteaza
}
};
struct Sector {
int inf; int sup;
vector<Segment> seg;
};
Sector s[NMAX]; int cnt;
int f[INF];
void read() {
fin >> n >> m;
for(int i = 1; i <= n; ++i)
fin >> pol[i].x >> pol[i].y;
for(int i = 1; i <= m ; ++i)
fin >> v[i].x >> v[i].y;
}
double det(point p1, point p2, point p3) {
return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
int sgn(Segment seg, point p) {
return det(seg.p1, seg.p2, p) < 0 ? -1 : 1;
}
int findSector(point p) {
int pos = 0 ; int step ;
for( step = 1; step <= cnt; step <<= 1);
for(pos = 0; step ; step >>= 1)
if(pos + step < cnt && s[pos + step].sup < p.x)
pos += step;
return pos + 1;
}
int count(Sector sector, point p) {
int pos; int step;
for(step = 1; step < sector.seg.size(); step <<=1 );
for(pos = 0; step ; step >>= 1)
if(pos + step < sector.seg.size()
&& sgn(sector.seg[pos + step], p) == -1)
pos += step;
return pos;
}
pointd intersection(int coordx, Segment seg) {
pointd p;
p.x = coordx;
p.y = 1.0 * (-seg.c - seg.a * coordx) / seg.b;
return p;
}
void solve() {
for(int i = 1 ; i <= n; ++i)
f[pol[i].x] = 1;
int start;
if(f[0] == 1)
start = 0;
else {
start = 1;
s[++cnt].inf = 0;
}
for(int i = start ; i < INF; ++i)
if(f[i])
s[++cnt].inf = i;
for(int i = 1; i < cnt; ++i)
s[i].sup = s[i + 1].inf;
s[cnt].sup = INF;
//for(int i = 1; i <= cnt; ++i)
// cout << s[i].inf << ' ' << s[i].sup << '\n';
pol[n + 1] = pol[1];
for(int i = 1; i <= cnt; ++i) {
//fiecare fasie
for(int j = 1; j <= n ; ++j) { //segment
if( (pol[j].x <= s[i].inf && s[i].sup <= pol[j + 1].x) ||
(pol[j + 1].x <= s[i].inf && s[i].sup <= pol[j].x) ) {
//cout << s[i].inf << ' ' << s[i].sup << ' ' << pol[j].x <<
//' ' << pol[j].y << ' ' << pol[j + 1].x << ' ' << pol[j + 1].y << '\n';
Segment seg = Segment(pol[j], pol[j + 1]);
pointd inter1 = intersection(s[i].inf, seg);
pointd inter2 = intersection(s[i].sup, seg);
s[i].seg.push_back(Segment(inter1, inter2));
}
}
sort(s[i].seg.begin(), s[i].seg.end());
}
int nrPoints = 0;
/*
for(int i = 1; i <= cnt; ++i)
for(Segment seg : s[i].seg)
cout << seg.p1.x << ' ' << seg.p1.y << ' ' << seg.p2.x << ' ' << seg.p2.y << '\n' << seg.middle.y << '\n';
*/
for(int i = 1; i <= m; ++i) {
int sec = findSector(v[i]);
if(count(s[sec], v[i]) % 2)
nrPoints++;
}
fout << nrPoints << '\n';
}
int main() {
read(); solve();
return 0;
}