Cod sursa(job #2062066)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 9 noiembrie 2017 22:39:08
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("camera.in");
ofstream fout ("camera.out");

const int Nmax = 2005, lim = 1e5;
const double eps = 1e-6;

struct Point
{
    double x, y;
    Point() {}
    Point(double _x, double _y) {x = _x, y = _y;}
};
vector< Point > a, v, new_v;
int n, i;

struct Dreapta
{
    double a, b, c;
    Dreapta(Point A, Point B)
    {
        a = B.y - A.y;
        b = A.x - B.x;
        c = A.y * B.x - A.x * B.y;
    }
};

double det(Point a, Point b, Point c)
{
    double res = a.x * b.y + b.x * c.y + c.x * a.y;
          res -= a.x * c.y + b.x * a.y + c.x * b.y;
    return res;
}

Point intersect(Dreapta d1, Dreapta d2)
{
    double x, y;
    x = (d2.c * d1.b - d1.c * d2.b) / (d1.a * d2.b - d2.a * d1.b);
    y = (d1.c * d2.a - d2.c * d1.a) / (d1.a * d2.b - d2.a * d1.b);
    return Point(x, y);
}

int sgn(double x)
{
    if(x < eps && x > -eps) return 0;
    if(x > eps) return 1;
    return -1;
}

void solve(Point a, Point b)
{
    int i, n = v.size();
    Dreapta d(a, b);
    v.push_back(v[0]);
    new_v.clear();
    int S1, S2;
    Point p;

    for(i=0; i<n; ++i)
    {
        S1 = sgn(det(a, b, v[i])), S2 = sgn(det(a, b, v[i+1]));
        p = intersect(Dreapta(v[i], v[i+1]), d);

        if(S1 * S2 == -1) new_v.push_back(p);
        if(S2 >= 0) new_v.push_back(v[i+1]);
    }
    v = new_v;
}

double area(vector<Point> a)
{
    int i;
    double ans = det(a.back(), a.front(), Point(0, 0));
    for(i=0; i<a.size()-1; ++i)
        ans += det(a[i], a[i+1], Point(0, 0));
    return ans;
}

int main()
{
    fin >> n;
    a.resize(n);
    for(i=0; i<n; ++i) fin >> a[i].x >> a[i].y;

    if(area(a) < 0) reverse(a.begin(), a.end());
    a.push_back(a[0]);

    v.push_back({-lim, -lim}); v.push_back({lim, -lim}); v.push_back({lim, lim}); v.push_back({-lim, lim});

    for(i=0; i<n && !v.empty(); ++i)
        solve(a[i], a[i+1]);

    if(v.empty())
    {
        fout << 0 << '\n';
        return 0;
    }

    double S = area(v);
    if(S < 0) S = -S; S /= 2;
    fout << setprecision(2) << fixed;
    fout << S << '\n';
    return 0;
}