Cod sursa(job #979784)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 2 august 2013 19:17:07
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#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);

}