Cod sursa(job #1718146)

Utilizator veleanduAlex Velea veleandu Data 16 iunie 2016 19:38:40
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <cmath>

using namespace std;

const int kMaxN = 805;

#define pb push_back
#define mp make_pair
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int n, m;
double x[kMaxN], y[kMaxN], from[kMaxN], to[kMaxN], fromX[kMaxN], dif[kMaxN];
int ox[kMaxN], oy[kMaxN], a[kMaxN], b[kMaxN];
LL c[kMaxN];
const double ANG = 0.12319212341941234901;
const double CANG = cos(ANG);
const double SANG = sin(ANG);
const double EPS = 1e-9;

int main() {
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    REP(i, n) {
        int tx, ty;
        scanf("%d%d", &tx, &ty);
        ox[i] = tx;
        oy[i] = ty;
        x[i] = CANG * tx - SANG * ty;
        y[i] = SANG * tx + CANG * ty;
    }
    x[n] = x[0];
    y[n] = y[0];
    ox[n] = ox[0];
    oy[n] = oy[0];
    REP(i, n) {
        a[i] = oy[i] - oy[i + 1];
        b[i] = ox[i + 1] - ox[i];
        c[i] = -((LL)a[i] * ox[i] + (LL)b[i] * oy[i]);
    }
    REP(i, n) {
        if (y[i] < y[i + 1]) {
            from[i] = y[i];
            to[i] = y[i + 1];
            dif[i] = (x[i + 1] - x[i]) / (to[i] - from[i]);
            fromX[i] = x[i] - dif[i] * from[i];
        } else {
            from[i] = y[i + 1];
            to[i] = y[i];
            dif[i] = (x[i] - x[i + 1]) / (to[i] - from[i]);
            fromX[i] = x[i + 1] - dif[i] * from[i];
        }
    }
    int ans = 0;
    REP(q, m) {
        int tx, ty;
        scanf("%d%d", &tx, &ty);
        bool boundary = false;
        REP(i, n) {
            if ((LL)a[i] * tx + (LL)b[i] * ty + c[i] == 0) {
                if (tx >= min(ox[i], ox[i + 1]) && tx <= max(ox[i], ox[i + 1])) {
                    if (ty >= min(oy[i], oy[i + 1]) && ty <= max(oy[i], oy[i + 1])) {
                        boundary = true;
                        break;
                    }
                }
            }
        }
        if (boundary) {
            ++ans;
            continue;
        }
        continue;
        double xx = CANG * tx - SANG * ty;
        double yy = SANG * tx + CANG * ty;
        int res = 0;
        REP(i, n) {
            if (yy > from[i] - EPS && yy < to[i] + EPS) {
                if (fromX[i] + dif[i] * yy > xx - EPS) {
                    res ^= 1;
                }
            }
        }
//        ans += res;
    }
    printf("%d\n", ans);
    return 0;
}