Cod sursa(job #1211624)

Utilizator 2dorTudor Ciurca 2dor Data 22 iulie 2014 22:40:40
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 4.62 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

ifstream fin("poligon.in");
ofstream fout("poligon.out");

const int MAXN = 809;
const int MAXM = 60009;
int N, M, Solution;
double SegmentMiddle[MAXN];//the middle of each segment
vector< vector<int> > Strips;

struct Point {
    double x, y;
    int indx;
    //indx = a pointer to the position of a point in the original
    //polygon order after it has been sorted by the x-coordinates, and vice-versa
}polygon[MAXN], crime[MAXM], aux[MAXM];
//polygon[] keeps the points on the polygon in their original order
//aux[] keeps the points sorted by the x-coordinates
//crime[] keeps the location of the crimes

struct cmp1 {
    bool operator() (const Point &A, const Point &B) const {
        return A.x < B.x;
    }
};

struct cmp2 {
    bool operator() (const int &A, const int &B) const {
        return SegmentMiddle[A] < SegmentMiddle[B];
    }
};

inline double Det(Point A, Point B, Point C) {
    if (B.x > C.x) swap(B, C);
    return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}

void Read() {
    fin >> N >> M;
    //read the polygon
    for (int i = 0; i < N; ++i) {
        fin >> polygon[i].x >> polygon[i].y;
        aux[i] = polygon[i];
        aux[i].indx = i;
    }
    polygon[N] = polygon[0];
    aux[N] = polygon[0];
    aux[N].indx = 0;
    /**I've inserted this axis as an invariant for the second
    binary search to work, even when the point has no edges beneath**/
    polygon[N + 1].x = 0, polygon[N + 1].y = -1;
    polygon[N + 2].x = 60001, polygon[N + 2].y = -1;
    //now an upper-bound
    polygon[N + 3].x = 0, polygon[N + 3].y = 60001;
    polygon[N + 4].x = 60001, polygon[N + 4].y = 60001;
    //read the crime points
    for (int i = 0; i < M; ++i)
        fin >> crime[i].x >> crime[i].y;
}

int BinarySearchStrip(int i) {
    Point P = crime[i];
    int Hi = N - 1, Lo = 0, Middle;
    while (Hi - Lo > 1) {
        Middle = (Hi + Lo) >> 1;
        //cerr << '\n' << aux[ Middle ].x << '\n';
        if (aux[ Middle ].x > P.x)
            Hi = Middle;
        else
            Lo = Middle;
    }
    return Lo;
}

int BinarySearchPosition(Point P, int Strip) {
    int Hi = Strips[Strip].size() - 1, Lo = 0, Middle;
    while (Hi - Lo > 1) {
        Middle = (Hi + Lo) >> 1;
        //cerr << "middle=" << Middle << '\n';
        if (Det(P, polygon[ Strips[Strip][Middle] ], polygon[ Strips[Strip][Middle] + 1 ]) > 0) {
            Lo = Middle;
        }else
        if (Det(P, polygon[ Strips[Strip][Middle] ], polygon[ Strips[Strip][Middle] + 1 ]) < 0) {
            Hi = Middle;
        }else {
            return 0;
        }
        //cerr << "Hi=" << Hi << " Lo=" << Lo << '\n';
    }
    return Lo;
}

void Solve() {
    Strips.resize(MAXN);
    //sort the points by the x-coordinate
    sort(aux, aux + N, cmp1());
    //mark where each point has moved to from the original index
    for (int i = 0; i < N; ++i)
        polygon[ aux[i].indx ].indx = i;
    polygon[N].indx = polygon[0].indx;
    //take each edge separately and insert it in the strips it passes through
    for (int i = 0; i < N; ++i) {
        Strips[i].push_back(N + 1);
        Strips[i].push_back(N + 3);
        for (int j = 0; j < N; ++j)
            if (min(polygon[j].x, polygon[j + 1].x) <= aux[i].x
                && aux[i].x < max(polygon[j].x, polygon[j + 1].x))
                Strips[i].push_back(j);
        /*if (polygon[i].x == polygon[i + 1].x) continue;//vertical*/
    }
    //calculate each segments' middle
    for (int i = 0; i <= N + 3; ++i)
        SegmentMiddle[i] = (polygon[i].y + polygon[i + 1].y) / 2;
    //sort the edges in each strip by their middle
    for (int i = 0; i < N; ++i)
        sort(Strips[i].begin(), Strips[i].end(), cmp2());

    /*for (int i = 0; i < N; ++i) {
        cerr << "Strip number " << i << ": ";
        for (size_t j = 0; j < Strips[i].size(); ++j) {
            cerr << Strips[i][j] << ' ';
        }cerr << '\n';
    }*/

    for (int i = 0; i < M; ++i) {
        if ((aux[N - 1].x <= crime[i].x) || (crime[i].x <= aux[0].x)) continue;
        int Strip = BinarySearchStrip(i);//which band the point is in
        //cerr << "Point #" << i << " is on Strip #" << Strip << '\n';
        int poz = BinarySearchPosition(crime[i], Strip);
        //cerr << "poz = " << poz << '\n';
        //cerr << '\n';
        Solution += poz % 2;
    }
}

void Write() {
    fout << Solution << '\n';
}

int main() {
    Read();
    Solve();
    Write();
    fin.close();
    fout.close();
    return 0;
}