Cod sursa(job #1044328)

Utilizator ericptsStavarache Petru Eric ericpts Data 29 noiembrie 2013 17:01:42
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.94 kb
#include <fstream>
#include <algorithm>
#include <set>
#include <vector>
#include <utility>
#include <iostream>

#define fun(x) ((int)(m * (x) + b))

using namespace std;

struct point{int x,y;};

const int MAX_N = 801;
const int MAX_M = 60001;

int n,m;

point poli[MAX_N];

point qry[MAX_M];

vector<int> zone;

vector< pair<point, point> > strip[MAX_N];

vector<int> no_dups(){
    set<int> T;

    for(int i = 1 ; i <= n ; ++i)
        T.insert(poli[i].x);

    return vector<int>(T.begin(), T.end());
}

void check(point const &A, point const &B, int const ind){

    if(B.x < A.x)
        return check(B, A, ind);

    if(A.x <= zone[ind] && zone[ind + 1] <= B.x){

        int const delX = B.x - A.x,
                  delY = B.y - A.y;

        if(delX == 0)
            return;

        strip[ind].push_back(make_pair(A, B));
    }
}

int ccw(point const &A, point const &B, point const &C){
    int const x1 = B.x - A.x,
              x2 = C.x - A.x;

    int const y1 = B.y - A.y,
              y2 = C.y - A.y;

    return x1 * y2 - x2 * y1;
}

int above(point const &P, pair<point, point> const &seg){
    int const cross = ccw(seg.first, seg.second, P);
    if(cross == 0)
        return -1;
    else return cross > 0;
}

bool comp(const pair<point, point> &A, const pair<point, point> &B){
    return (bool)above(A.first, B) || (bool)above(A.second, B);
}

void preprocess(){
    zone = no_dups();
    for(size_t z = 0 ; z < zone.size() - 1 ; ++z){
        for(int i = 0 ; i < n ; ++i)
            check(poli[i], poli[(i+1) % n], z);
        sort(strip[z].begin(), strip[z].end(), comp);
        reverse(strip[z].begin(), strip[z].end());
    }
}

bool cmp(const point &A, const point &B){
    return A.x < B.x;}

void read(){
    ifstream in("poligon.in");

    in >> n >> m;


    for(int i = 0 ; i < n ; ++i)
        in >> poli[i].x >> poli[i].y;

    for(int i = 1 ; i <= m ; ++i)
        in >> qry[i].x >> qry[i].y;

}

bool bsearch(point const &P, int const idx){
    int i;
    size_t step;

    for(step = 1 ; step <= strip[idx].size() ; step <<= 1);

    bool on_side = 0;

    for(i = -1 ; step ; step >>= 1){
        if(i + step < strip[idx].size()){
            int const cnd = above(P, strip[idx][i + step]);

            if(cnd == -1)
                on_side = 1;

            else if(cnd)
                i += step;
        }
    }
    return ((i + 1) % 2 == 1) || on_side;
}

int main(){

    read();
    preprocess();
    sort(qry + 1, qry + m + 1, cmp);

    int tot = 0;
    size_t now = 0;

    for(int i = 1 ; i <= m ; ++i){

        while(qry[i].x < zone[now] && i <= m)
            ++i;

        while(zone[now + 1] < qry[i].x && now < zone.size() - 1)
            ++now;

        if(i <= m && now < zone.size() - 1)
            tot += bsearch(qry[i], now);
    }

    ofstream out("poligon.out");
    out << tot << "\n";
}