Pagini recente » Cod sursa (job #1765178) | Cod sursa (job #1780559) | Cod sursa (job #2302777) | Cod sursa (job #1165150) | Cod sursa (job #979784)
Cod sursa(job #979784)
#include <cstdio>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair <int, int> point;
const int NMAX = 803;
point V[NMAX];
long long s;
double m[NMAX];
double panta (point a, point b) {
return (double)(b.y - a.y) / (b.x - a.y);
}
bool isin (point q, point a, point b, point c) {
bool k = a.x * (b.y - q.y) + b.x * (q.y - a.y) + q.x * (a.y - b.y) <= 0;
if ((b.x * (c.y - q.y) + c.x * (q.y - b.y) + q.x * (b.y - c.y) <= 0) != k)
return 0;
if ((c.x * (a.y - q.y) + a.x * (q.y - c.y) + q.x * (c.y - a.y) <= 0) != k)
return 0;
return 1;
}
int main () {
freopen ("poligon.in", "r", stdin);
freopen ("poligon.out", "w", stdout);
point q;
int N, M, i, p = 1, j = 0;
scanf ("%d%d%d%d", &N, &M, &V[1].x, &V[1].y);
for (i = 2; i <= N; ++i) {
scanf ("%d%d", &V[i].x, &V[i].y);
s += V[i - 1].x * V[i].y - V[i - 1].y * V[i].x;
if (V[p] > V[i])
p = i;
}
s += V[N].x * V[1].y - V[N].y * V[1].x;
if (s < 0)
p = N - p + 1,
reverse (V + 1, V + N + 1);
for (i = p + 1; i <= N; ++i)
m[++j] = panta (V[p], V[i]);
for (i = 1; i < p; ++i)
m[++j] = panta (V[p], V[i]);
j = 0;
while (M--) {
scanf ("%d%d", &q.x, &q.y);
i = lower_bound (m + 1, m + N, panta (V[p], q)) - m;
if (i == 1)
continue;
j += isin (q, V[i], V[i - 1], V[p]);
}
printf ("%d", j);
}