Cod sursa(job #2059827)

Utilizator retrogradLucian Bicsi retrograd Data 7 noiembrie 2017 17:36:08
Problema Camera Scor 40
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.57 kb
#include <bits/stdc++.h>

using namespace std;

using Point = complex<double>;

double cross(Point a, Point b) { return (conj(a) * b).imag(); }
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);
    return (c1 * q - c2 * p) / (c1 - c2);
}

vector<Point> PolygonCut(const vector<Point>& P, Point s, Point e) {
    vector<Point> res;
    for (int i = 0; i < (int)P.size(); ++i) {
        Point cur = P[i], prev = i ? P[i - 1] : P.back();
        bool side = det(s, e, cur) > 0;
        if (side != (det(s, e, prev) > 0)) {
            res.push_back(LineIntersection(s, e, cur, prev));
        }
        if (side) res.push_back(cur);
    }
    return res;
}

double Area(const vector<Point>& P) {
    int n = P.size(); double ret = 0;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        ret += cross(P[j], P[i]);
    }
    return ret;
}

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

    int n; cin >> n;

    vector<Point> P(n);
    for (int i = 0; i < n; ++i) {
        double x, y; cin >> x >> y;
        P[i] = Point(x, y);
    }

    if (Area(P) < 0) 
        reverse(P.begin(), P.end());

    vector<Point> kern = {Point{-1e9, -1e9}, Point{1e9, -1e9}, 
                          Point{1e9, 1e9}, Point{-1e9, 1e9}};
    assert(Area(kern) > 0);
    
    for (int j = n - 1, i = 0; i < n; j = i++) {
        kern = PolygonCut(move(kern), P[j], P[i]);
    }
    cout << fixed << setprecision(20) << .5 * Area(kern) << endl;


    return 0;
}