Cod sursa(job #2022547)

Utilizator vlecomteVictor Lecomte vlecomte Data 16 septembrie 2017 18:39:32
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 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 D(i,n) for (int i=(n); --i>=0;)
#define DX(i,a,b) for (int i=(b); --i>=(a);)
#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;

typedef complex<int> C;
#define x real()
#define y imag()
int cross(C a, C b) {return (conj(a)*b).y;}
int orient(C a, C b, C c) {return cross(b-a, c-a);}
struct ab {C a,b;};

ifstream fin("poligon.in");
ofstream fout("poligon.out");
C r() {int a,b; fin>>a>>b; return {a,b};}

signed main() {
    int n,m; fin>>n>>m;
    //H(sizeof(C));
    V<C> ps(n);
    F(i,n) ps[i]=r();
    V<int> xs(n);
    F(i,n) xs[i] = ps[i].x;
    sort(ALL(xs));
    xs.resize(unique(ALL(xs)) - xs.begin());
    V<V<ab>> through(S(xs)), vert(S(xs));
    return 0;
    //P("A");
    F(i,n) {
        C a=ps[i], b=ps[(i+1)%n];
        if (a.x > b.x || (a.x == b.x && a.y > b.y))
            swap(a,b);
        int ia = lower_bound(ALL(xs), a.x) - xs.begin(),
            ib = lower_bound(ALL(xs), b.x) - xs.begin();
        FX(j,ia,ib)
            through[j].pb({a,b});
        if (ia == ib)
            vert[ia].pb({a,b});
    }
    F(j,S(xs))
        assert(S(through[j])%2 == 0);
    //P("B");
    F(i,S(xs)) {
        sort(ALL(through[i]), [](ab p, ab q) {
            return orient(p.a, p.b, q.a) > 0 || orient(p.a, p.b, q.b) > 0;});
        sort(ALL(vert[i]), [](ab p, ab q) {
            return p.a.y < q.a.y;});
    }
    return 0;
    int tot=0;
    F(qq,m) {
        C a=r();
        int j = upper_bound(ALL(xs), a.x) - xs.begin() - 1;
        bool in=false;
        if (j >= 0) {
            //H(qq);
            //H(j);
            if (xs[j] == a.x) {
                //P("test vert");
                //for (ab p : vert[j]) cout<<p.a.y<<' '<<p.b.y<<endl;
                auto it = lower_bound(ALL(vert[j]), a, [](ab p, C q) {
                    return p.b.y < q.y;});
                if (it != vert[j].end() && it->a.y <= a.y && a.y <= it->b.y)
                    in = true;
            }
            auto it = lower_bound(ALL(through[j]), a, [](ab p, C q) {
                return orient(p.a, p.b, q) > 0;});
            if ((it - through[j].begin())%2 || (it != through[j].end() && orient(it->a, it->b, a) == 0))
                in = true;
            tot += in;
        }
        //H(in);
        //P("");
    }
    fout<<tot<<"\n";
}