Cod sursa(job #1420480)

Utilizator assa98Andrei Stanciu assa98 Data 18 aprilie 2015 16:11:31
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <fstream>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <vector>

#define pe pair<double, double>
#define fi first
#define se second
#define mp make_pair

using namespace std;

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

const double PI = 3.14159265359;
const double INF = 10e6;
const int MAX_N = 810;
const double eps = 10e-6;

class cmp {
public:
    inline bool operator() (const pe &a, const pe &b) const {
        return a.fi + a.se < b.fi + b.se;
    }
};

pe R;

inline pe rot(pe x) {
    return mp(x.fi * R.fi - x.se * R.se, x.se * R.fi + x.fi * R.se);
}

vector<pe> pol;
vector<double> fas;

vector<pe> A[MAX_N];

inline double getY(double x, pe p1, pe p2) {
    return (p1.se * (p2.fi - p1.fi) - (p1.fi  - x) * (p2.se - p1.se)) / (p2.fi - p1.fi);
}

inline pe intersect(double x1, double x2, pe p1, pe p2) {
    if(p1.fi > p2.fi) {
        swap(p1, p2);
    }
    
    if(x1 < p1.fi || x2 > p2.fi) {
        return mp(-INF, -INF);
    }

    return mp(getY(x1, p1, p2), getY(x2, p1, p2));
}

void pregen() {
    pol.push_back(pol[0]);
    for(auto it : pol) {
        fas.push_back(it.fi);
    }
    
    sort(fas.begin(), fas.end());
    fas.erase(unique(fas.begin(), fas.end()), fas.end());
    for(int i = 1; i < (int)fas.size(); i++) {
        for(int j = 1; j < (int)pol.size(); j++) {
            pe x = intersect(fas[i - 1], fas[i], pol[j - 1], pol[j]);
            if(x != mp(-INF, -INF)) {
                A[i].push_back(x);
            }
        }
        sort(A[i].begin(), A[i].end(), cmp());
    }
}

int search(int poz, pe p) {
    int st = 0;
    int dr = A[poz].size() - 1;
    int ans = -1;
    while(st <= dr) {
        int mij = (st + dr) / 2;
        double y = getY(p.fi, mp(fas[poz - 1], A[poz][mij].fi), mp(fas[poz], A[poz][mij].se));
        if(p.se > y + eps) {
            ans = mij;
            dr = mij - 1;
        }
        else if(p.se < y - eps) {
            st = mij + 1;
        }
        else {
            return 1;
        }
    }
    return ans + 1;
}

bool query(pe p) {
    if(p.fi < fas[0] || p.se > fas[fas.size() - 1]) {
        return false;
    }
    int ind = lower_bound(fas.begin(), fas.end(), p.fi) - fas.begin();
    return search(ind, p) % 2; 
}

int main() {
    srand(time(NULL));
    double ur = (double)(rand() % 10000) / 10000 * PI;
    R = mp(cos(ur), sin(ur));
    
    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= n; i++) {
        double x, y;
        fin >> x >> y;
        pol.push_back(rot(mp(x, y)));
    }

    pregen();

    int ans = 0;

    for(int i = 1; i <= m; i++) {
        pe x;
        fin >> x.fi >> x.se;
        x = rot(x);
        ans += query(x);
    }

    fout << ans;

    return 0;
}