Cod sursa(job #2190609)

Utilizator losesUNIBUC Lacheta loses Data 31 martie 2018 12:18:56
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.92 kb
#include <bits/stdc++.h>
 
using namespace std;
#define DOUBLE double
 
const double kInf = 2.0e5;
struct Point { 
    DOUBLE x, y; 
    Point operator+(const Point& oth) const { return {x + oth.x, y + oth.y}; }
    Point operator-(const Point& oth) const { return {x - oth.x, y - oth.y}; }
    Point operator*(const DOUBLE d) const { return {x * d, y * d}; }
    Point operator/(const DOUBLE d) const { return {x / d, y / d}; }
};
int sgn(DOUBLE d) { return max(d, -d) < 1e-5 ? 0 : d < 0 ? -1 : 1; }
DOUBLE cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
DOUBLE dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
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(c2 - c1));
  return (q * c1 - p * c2) / (c1 - c2);
}
 
struct Angle {
    long long x, y;
    Angle(long long x, long long y) : x(x), y(y) {}
    Angle operator-(Angle a) const { return {x-a.x, y-a.y}; }
    int quad() const {
        if (y < 0) return (x >= 0) + 2;
        if (y > 0) return (x <= 0);
        return (x <= 0) * 2;
    }
    Point p() const { return {1. * x, 1. * y}; }
    Angle t90() const { return {-y, x}; }
};
bool operator<(Angle a, Angle b) {
    return make_pair(a.quad(), a.y * b.x) <
           make_pair(b.quad(), a.x * b.y);
}
 
struct HalfplaneSet : multimap<Angle, Point> {
    using Iter = multimap<Angle, Point>::iterator;
    
    HalfplaneSet() { 
        insert({{+1, 0}, {-kInf, -kInf}});
        insert({{0, +1}, {+kInf, -kInf}});
        insert({{-1, 0}, {+kInf, +kInf}});
        insert({{0, -1}, {-kInf, +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(Angle a, Angle b) {
        if (empty()) return;
        int old_size = size();
 
        auto eval = [&](Iter it) { return sgn(det(a.p(), b.p(), it->second)); };
        auto intersect = [&](Iter it)  { 
            return LineIntersection(a.p(), b.p(), 
                    it->second, it->first.p() + it->second); 
        }; 
 
        auto it = fix(lower_bound(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->second = intersect(it); 
        else it = fix(erase(it));
        
        if (old_size <= 2) return;
 
        it = get_prev(it);
        auto p = intersect(it);
        
        insert(it, {b - a, p});
        if (eval(it) == 0) erase(it);
    }
    
    DOUBLE Maximize(Angle c) {
        assert(!empty());
        auto it = fix(lower_bound(c.t90()));
        return dot(it->second, c.p());
    }
 
    void output() {
        cerr << "Polygon\n";
        for (auto x : *this) {
            cerr << x.second.x << " " << x.second.y << '\n';
            cerr << "dir: " << x.first.x << " " << x.first.y << '\n';
        }
        cerr << "...\n";
    }
    
    DOUBLE Area() {
        if (size() <= 2) return 0;
        DOUBLE ret = 0;
        for (auto it = begin(); it != end(); ++it)
            ret += cross(it->second, get_next(it)->second);
        return ret;
    }
};
 
int main() {
    ifstream cin("camera.in");
    ofstream cout("camera.out");

    int n; cin >> n;
    vector<Angle> P;
    for (int i = 0; i < n; ++i) {
        long long x, y; cin >> x >> y;
        P.emplace_back(x, y);
    }

    DOUBLE ans = 0;
    for (int it = 0; it < 2; ++it) {
        HalfplaneSet hs;
        for (int i = 0, j = n - 1; i < n; j = i++) {
            hs.Cut(P[j], P[i]);
        }
        ans = max(ans, hs.Area());
        reverse(P.begin(), P.end());
    }
    cout << fixed << setprecision(2) << ans / 2. << endl;
}