Cod sursa(job #898107)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 28 februarie 2013 00:45:42
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.38 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstdio>

#define PDD pair<double, double>
#define mp make_pair
#define x first
#define y second
#define MAX 805
#define MMAX 60005
#define BMAX 1000000
#define EPS 1e-8

using namespace std;

int N, M, ans, poz;
double A[MAX];
char buff[BMAX];
PDD V[MAX], W[MMAX], lInt[MAX], rInt[MAX];

inline double det(const PDD &A, const PDD &B, const PDD &C) {
    return A.x * B.y + B.x * C.y + C.x * A.y - A.y * B.x - B.y * C.x - C.y * A.x;
}

inline int CMP(const double &X, const double &Y) {
    if(X + EPS < Y) return -1;
    if(Y + EPS < X) return 1;
    return 0;
}

inline bool cmp(const PDD &X, const PDD &Y) {
    return CMP(X.y, Y.y) < 0;
}

inline PDD intersect(const PDD &where, const PDD &A, const PDD &B) {
    return mp(where.x, B.y + (B.y - A.y) * (where.x - B.x) / (B.x - A.x));
}

PDD rotate(const PDD &A, const double angle) {
    double X, Y;
    X = A.x * cos(angle) - A.y * sin(angle);
    Y = A.x * sin(angle) + A.y * cos(angle);
    return mp(X, Y);
}

void cit(int &X) {
    while(buff[poz] < '0' || buff[poz] > '9')
        if(++poz == BMAX) fread(buff, 1, BMAX, stdin), poz = 0;
    X = 0;
    while(buff[poz] >= '0' && buff[poz] <= '9') {
        X = X * 10 + buff[poz++] - '0';
        if(poz == BMAX) fread(buff, 1, BMAX, stdin), poz = 0;
    }
}

void citire() {
    freopen("poligon.in", "r", stdin); fread(buff, 1, BMAX, stdin);
    cit(N); cit(M);
    for(int i = 1, a, b; i <= N; i++) {
        cit(a); cit(b);
        V[i].x = a, V[i].y = b;
        V[i] = rotate(V[i], 0.002);
        A[i] = V[i].x;
    } V[N + 1] = V[1];
    /*for(int i = 1; i <= N; i++)
        cout<<V[i].x<<" "<<V[i].y<<"\n";*/
    for(int i = 1, a, b; i <= M; i++) {
        cit(a); cit(b);
        W[i].x = a, W[i].y = b;
        W[i] = rotate(W[i], 0.002);
    } fclose(stdin);
}

int main() {
    citire();
    sort(A + 1, A + N + 1);
    sort(W + 1, W + M + 1);
    for(int i = 1, poz = 1; i < N; i++) {
        if(!CMP(A[i], A[i + 1])) continue;
        PDD lTop = mp(A[i], 60001.0), lBot = mp(A[i], -1.0), rTop = mp(A[i + 1], 60001.0), rBot = mp(A[i + 1], -1.0);
        int nr = 0;
        for(int j = 1; j <= N; j++) {
            if(V[j].x <= A[i] && V[j + 1].x <= A[i]) continue;
            if(V[j].x >= A[i + 1] && V[j + 1].x >= A[i + 1]) continue;
            lInt[++nr] = intersect(lBot, V[j], V[j + 1]);
            rInt[nr]   = intersect(rBot, V[j], V[j + 1]);
        }
        sort(lInt + 1, lInt + nr + 1, cmp);
        sort(rInt + 1, rInt + nr + 1, cmp);
        while(poz <= M && CMP(W[poz].x, A[i + 1]) < 0) {
            int sol = 0;
            for(int step = (1 << 9); step; step >>= 1)
                if(sol + step <= nr && det(lInt[sol + step], rInt[sol + step], W[poz]) >= -EPS) sol |= step;
            if(!sol) {
                ++poz;
                continue;
            }
            if(sol & 1) {
                ans++;
                poz++;
                continue;
            }
            double semn = det(lInt[sol], rInt[sol], W[poz]);
            if(CMP(semn, 0.0) == 0) {
                ans++;
                poz++;
                continue;
            }
            poz++;
        }
    }
    freopen("poligon.out", "w", stdout); printf("%d\n", ans); fclose(stdout);
    return 0;
}