Pagini recente » Cod sursa (job #544650) | Cod sursa (job #1044597) | Cod sursa (job #2595627) | Cod sursa (job #3274039) | Cod sursa (job #773933)
Cod sursa(job #773933)
#include <cstdio>
#include <algorithm>
using namespace std;
struct punct {
int x,y;
};
struct intersectie {
double y1, y2, mid;
};
const int N = 805;
const double EPS = 1e-10;
const int INF = 0x3f3f3f3f;
int n, m, a, b, fasie, sol, fasii;
int x[N], nr[N];
punct p[N];
intersectie intersectii[N][N];
inline int cmp (intersectie a, intersectie b)
{
if (a.mid + EPS < b.mid)
return 1;
return 0;
}
inline void makeStrips()
{
for (int i = 1; i < fasii; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j].x <= x[i] && x[i + 1] <= p[j + 1].x) {
double alfa, x1, x2, y1, y2;
alfa = (double)(p[j + 1].y - p[j].y) / (double)(p[j + 1].x - p[j].x);
x1 = x[i];
y1 = alfa * (x1 - p[j].x) + p[j].y;
x2 = x[i + 1];
y2 = alfa * (x2 - p[j].x) + p[j].y;
//intersectii[i][++nr[i]] = {y1, y2, (y1 + y2) / 2};
intersectii[i][++nr[i]].y1 = y1;
intersectii[i][nr[i]].y2 = y2;
intersectii[i][nr[i]].mid = (y1 + y2) / 2.0;
}
}
sort(intersectii[i] + 1, intersectii[i] + nr[i] + 1, cmp);
}
}
inline int cauta_fasie(int a, int b)
{
int l, r;
l = 1;
r = fasii - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (x[mid] <= a && a <= x[mid + 1])
return mid;
if (a < x[mid])
r = mid - 1;
else if (a > x[mid + 1])
l = mid + 1;
}
}
inline int verifica(int a, int b, int fasie)
{
int l, r;
l = 1;
r = nr[fasie];
while (l <= r) {
int mid = l + (r - l) / 2;
double x1 = x[fasie], x2 = x[fasie + 1];
double y1 = intersectii[fasie][mid].y1, y2 = intersectii[fasie][mid].y2;
double det1 = x1 * y2 + y1 * a + x2 * b - a * y2 - x2 * y1 - b * x1;
y1 = intersectii[fasie][mid + 1].y1;
y2 = intersectii[fasie][mid + 1].y2;
double det2 = x1 * y2 + y1 * a + x2 * b - a * y2 - x2 * y1 - b * x1;
if (det1 < EPS || det2 < EPS)
return 1;
if (det1 + EPS < 0.0 && det2 - EPS > 0.0) {
if (mid % 2 == 0)
return 0;
else return 1;
}
if (det1 - EPS > 0.0)
r = mid - 1;
else if (det2 + EPS < 0.0)
l = mid + 1;
}
return 0;
}
int main()
{
freopen ("poligon.in", "r", stdin);
freopen ("poligon.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d %d", &p[i].x, &p[i].y);
x[i] = p[i].x;
}
p[n + 1] = p[1];
sort(x + 1, x + n + 1);
x[n + 1] = INF;
for (int i = 1; i <= n; ++i)
if (x[i] != x[i + 1])
x[++x[0]] = x[i];
fasii = x[0];
makeStrips();
for (int i = 1; i <= m; ++i) {
scanf("%d %d", &a, &b);
fasie = cauta_fasie(a, b);
if (verifica(a, b, fasie)) {
++sol;
fprintf(stderr, "%d ", i);
}
}
printf("%d", sol);
return 0;
}