Mai intai trebuie sa te autentifici.

Cod sursa(job #2190531)

Utilizator losesUNIBUC Lacheta loses Data 31 martie 2018 02:23:25
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.49 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); }
 
 
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) {
    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 { 
    mutable Point data;
    mutable Point dir;
    bool operator<(const Node& oth) const {
        return CompareAngles(dir, oth.dir) < 0;
    }
    Node(Point data, Point dir) : data(data), dir(dir) {}
};
 
struct HalfplaneSet : set<Node> {
    using Iter = set<Node>::iterator;
    
    HalfplaneSet() { 
        insert(Node{{-kInf, -kInf}, {+2*kInf, 0}});
        insert(Node{{+kInf, -kInf}, {0, +2*kInf}});
        insert(Node{{+kInf, +kInf}, {-2*kInf, 0}});
        insert(Node{{-kInf, +kInf}, {0, -2*kInf}});
    }
 
    Iter get_next(Iter it) { return (next(it) == end() ? begin() : next(it)); }
    Iter get_prev(Iter it) { return (it == begin() ? prev(end()) : prev(it)); } 
    Iter fix(Iter it) { return it == end() ? begin() : it; } 
     
    void Cut(Point a, Point b) {
        if (empty()) return;
        auto eval = [&](Iter it) { return sgn(det(a, b, it->data)); };
        
        auto it = fix(lower_bound(Node{0, b - a}));
        
        if (eval(it) >= 0) return;
        
        while (size() && eval(get_prev(it)) < 0) fix(erase(get_prev(it)));
        while (size() && eval(get_next(it)) < 0) it = fix(erase(it));
        
        if (empty()) return;

        
        if (eval(get_next(it)) > 0) {
            it->data = LineIntersection(a, b, it->data, get_next(it)->data);
        } else it = fix(erase(it));
        
                 
        it = get_prev(it);
        if (eval(it) > 0) {
            auto p = LineIntersection(a, b, it->data, it->data + it->dir);
            insert(Node{p, get_next(it)->data - p});
        } 
        it->dir = get_next(it)->data - it->data;
    }
 
    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() { 
        cerr << "Polygon\n";
        for (auto itr : *this) {
            cerr << itr.data.real() << " " << itr.data.imag() << '\n';
        }
        cerr << "...\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;
}