Cod sursa(job #2190516)

Utilizator losesUNIBUC Lacheta loses Data 31 martie 2018 00:36:03
Problema Camera Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.08 kb
#include <bits/stdc++.h>

using namespace std;

using Point = complex<double>;

const double kInf = 2e5;
int sgn(double d) { return abs(d) < 1e-6 ? 0 : d < 0 ? -1 : 1; }
double cross(Point a, Point b) { return (conj(a) * b).imag(); }
double dot(Point a, Point b) { return (conj(a) * b).real(); }
double det(Point a, Point b, Point c) { return cross(b - a, c - a); }
int sdet(Point a, Point b, Point c) { return sgn(det(a, b, c)); }


Point LineIntersection(Point a, Point b, Point p, Point q) {
  double c1 = det(a, b, p), c2 = det(a, b, q);
  assert(sgn(c1 - c2)); // undefined if parallel
  return (c1 * q - c2 * p) / (c1 - c2);
}
int Quad(Point p) {
    double x = p.real(), y = p.imag();
    if (sgn(y) < 0) return (sgn(x) >= 0) + 2;
    if (sgn(y) > 0) return (sgn(x) <= 0);
    return (sgn(x) < 0) * 2;
}
int CompareAngles(Point a, Point b) {
    if (sgn(norm(a)) == 0) return -1;
    if (sgn(norm(b)) == 0) return 1;
    int qa = Quad(a), qb = Quad(b);
    if (qa != qb) return qa < qb ? -1 : 1;
    int sc = sgn(cross(a, b));
    if (sc != 0) return -sc;
    return sgn(dot(a, a) - dot(b, b)); 
}

struct Node { 
    Point data; mutable Point dir; 
    static function<int(Node, Node)> COMPARE;
    bool operator<(const Node& oth) const {
        return COMPARE(*this, oth) < 0;
    }
};
function<int(Node, Node)> Node::COMPARE;

struct HalfplaneSet : set<Node> {
    using Iter = set<Node>::iterator;
    Point leftmost = 0; 
    function<int(Node, Node)> UCMP, QCMP;

    HalfplaneSet() { 
        UCMP = [&](Node a, Node b) { 
            return CompareAngles(a.data - leftmost, b.data - leftmost);
        };
        QCMP = [&](Node a, Node b) { 
            return CompareAngles(a.dir, b.dir); 
        };

        for (int i = 0; i < 4; ++i) {
            double x = -kInf, y = -kInf;
            if (i & 1) x *= -1;
            if (i & 2) y *= -1;    
            do_insert({x, y});
        }
    }

    Iter get_next(Iter it) { return (next(it) == end() ? begin() : next(it)); }
    Iter get_prev(Iter it) { return (it == begin() ? prev(end()) : prev(it)); }

    void update(Iter it) { if (it != end()) it->dir = get_next(it)->data - it->data; }
    
    Iter do_erase(Iter it) {
        ::swap(Node::COMPARE, UCMP);
        Iter ret = erase(it); 
        if (ret == end()) ret = begin();
        update(ret); update(get_prev(ret));
        leftmost = empty() ? 0 : begin()->data;
        
        ::swap(Node::COMPARE, UCMP);
        return ret;
    }
    Iter do_insert(Point p) {
        ::swap(Node::COMPARE, UCMP);
        int dx = sgn(p.real() - leftmost.real());
        int dy = sgn(p.imag() - leftmost.imag());
        if (dy < 0 or (dy == 0 && dx < 0)) leftmost = p;

        Iter ret = insert(Node{p, 0}).first;
        update(ret); update(get_prev(ret));
        ::swap(Node::COMPARE, UCMP);
        return ret;
    }

    void Cut(Point s, Point e) {
        ::swap(Node::COMPARE, QCMP);
        cut(s, e);
        ::swap(Node::COMPARE, QCMP); 
    }

    void cut(Point a, Point b) {
        if (empty()) return;

        auto eval = [&](Iter it) { return sdet(a, b, it->data); };
        auto fst = lower_bound(Node{0, b - a});
        if (fst == end()) fst = begin();
        auto lst = fst;
        

//        cerr << a << " " << b << endl;
        if (eval(fst) >= 0) return;
        
        size_t iters = 0;
        while (iters < 2 * size()) {
            ++iters;
            if (eval(get_next(lst)) < 0) { lst = get_next(lst); continue; }
            if (eval(get_prev(fst)) < 0) { fst = get_prev(fst); continue; }
            break;
        }
        
        vector<Point> to_insert;
        if (iters > size()) { 
            clear(); return; 
        }
        if (eval(get_prev(fst)) > 0) 
            to_insert.push_back(LineIntersection(a, b, fst->data, get_prev(fst)->data));
        if (eval(get_next(lst)) > 0)
            to_insert.push_back(LineIntersection(a, b, lst->data, get_next(lst)->data));
        
//        cerr << "BEFORE:\n"; output();     
        while (fst != lst)
            fst = do_erase(fst);
        fst = do_erase(fst);
//        cerr << "MIDWAY:\n"; output();
        for (auto x : to_insert)
            do_insert(x);
//        cerr << "AFTER:\n"; output();

    }

    double Area() {
        double ret = 0;
        for (auto it = begin(); it != end(); ++it)
            ret += cross(it->data, get_next(it)->data);
        return abs(ret);
    }

    void output() { 
        cout << "Polygon\n";
        for (auto itr : *this) {
            cout << itr.data.real() << " " << itr.data.imag() << '\n';
        }
        cout << "...\n";
    }
};

int main() {
    ifstream cin("camera.in");
    ofstream cout("camera.out");

    int n; cin >> n;
    vector<Point> P;
    
    for (int i = 0; i < n; ++i) {
        double x, y; cin >> x >> y; 
        P.emplace_back(x, y);
    }
    
    
    double ans = 0;
    for (int it = 0; it < 2; ++it) {
        HalfplaneSet s;
        for (int j = n - 1, i = 0; i < n; j = i++) {
            s.Cut(P[j], P[i]);
        }
        ans = max(ans, s.Area());
        // s.output();
        reverse(P.begin(), P.end());
    }
    
    cout << fixed << setprecision(2) << ans / 2 << endl;
}