Cod sursa(job #2030094)

Utilizator vlecomteVictor Lecomte vlecomte Data 1 octombrie 2017 03:13:55
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <bits/stdc++.h>
#define int long long
#define P(x) cout << x << endl
#define H(x) P(#x << ": " << x)
#define F(i,n) for (int i=0; i<(n); i++)
#define FE(i,n) for (int i=0; i<=(n); i++)
#define FX(i,a,b) for (int i=(a); i<(b); i++)
#define FI(i,a,b) for (int i=(a); i<=(b); i++)
#define D(i,n) for (int i=(n); --i>=0;)
#define DE(i,n) for (int i=(n); i>=0; i--)
#define DX(i,a,b) for (int i=(b); --i>=(a);)
#define DI(i,a,b) for (int i=(b); i>=(a); i--)
#define S(s) (int)(s).size()
#define ALL(v) v.begin(), v.end()
#define MI(a,v) a = min(a,(v))
#define MA(a,v) a = max(a,(v))
#define V vector
#define pb push_back
#define mt make_tuple
using namespace std;

#ifndef LOCAL
ifstream fin("poligon.in");
ofstream fout("poligon.out");
#define cin fin
#define cout fout
#endif

#define double long double
typedef complex<double> pt;
#define x real()
#define y imag()
pt r() {double a,b; cin>>a>>b; return {a,b};}
double EPS=1e-9;
bool lt(double a, double b) {return a + EPS < b;}

struct lfun {
    double a,b;
    lfun(pt p, pt q) : a((q.y-p.y)/(q.x-p.x)), b(p.y-a*p.x) {}
    double operator()(double xx) {return a*xx+b;}
};
const pt rot=polar(1.0,1.0);
auto cmp = [](pt a, pt b) {return mt(a.x,a.y) < mt(b.x,b.y);};
struct region {
    V<double> xs;
    V<V<lfun>> segs;
    set<pt, decltype(cmp)> orig;
    region(V<pt> ps) : orig(cmp) {
        for (pt &p : ps) {
            orig.insert(p);
            p *= rot;
            xs.pb(p.x);
            //H(p);
        }
        sort(ALL(xs));
        segs.resize(S(ps)-1);
        F(i,S(segs)) {
            double l=xs[i], r=xs[i+1], mid=(l+r)/2;
            F(j,S(ps)) {
                pt a=ps[j], b=ps[(j+1)%S(ps)];
                if (min(a.x,b.x) <= l && r <= max(a.x,b.x))
                    segs[i].pb({a,b});
            }
            //H(S(segs[i]));
            sort(ALL(segs[i]), [&](lfun f, lfun g) {return f(mid) < g(mid);});
        }
    }
    bool in(pt p) { // undefined if p on perimeter
        if (orig.count(p)) return true;
        p *= rot;
        auto it = lower_bound(ALL(xs), p.x);
        if (it == xs.begin() || it == xs.end()) return false;
        V<lfun> &a = segs[it-xs.begin()-1];
        auto lb = lower_bound(ALL(a), p, [](lfun f, pt q) {return lt(f(q.x), q.y);}),
             ub = upper_bound(ALL(a), p, [](pt q, lfun f) {return lt(q.y, f(q.x));});
        if (lb != ub) return true;
        return (lb - a.begin()) % 2;
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m; cin>>n>>m;
    V<pt> ps(n);
    F(i,n) ps[i] = r();
    region reg(ps);
    int tot=0;
    F(q,m) {
        bool res = reg.in(r());
        //H(res);
        tot += res;
    }
    P(tot);
}