Cod sursa(job #2507745)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 10 decembrie 2019 19:34:55
Problema Camera Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.18 kb
#include <fstream>
#include <iomanip>
#define xx first
#define yy second
#define eps 0.000001
#define INF 100010

using namespace std;

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

int n,i,j;
pair<double, double> v[2005],p[2005],aux[2005];

double det(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
    double D = (b.xx-a.xx)*(c.yy-a.yy)-(c.xx-a.xx)*(b.yy-a.yy);
    if (D >= -eps && D <= eps)
        return 0;
    else
        return D;
}

pair<double, double> intersectDr(pair<double, double> a, pair<double, double> b, pair<double, double> c, pair<double, double> d)
{
    double a1 = b.yy-a.yy; double b1 = a.xx-b.xx; double c1 = a.yy*(b.xx-a.xx)-a.xx*(b.yy-a.yy);
    double a2 = d.yy-c.yy; double b2 = c.xx-d.xx; double c2 = c.yy*(d.xx-c.xx)-c.xx*(d.yy-c.yy);
    return make_pair((b1*c2-b2*c1)/(b2*a1-b1*a2), (a1*c2-a2*c1)/(a2*b1-a1*b2));
}

int main()
{
    fin >> n;
    pair<double, double> origine = make_pair(0, 0);
    pair<double, double> inf = make_pair(INF, INF);
    double xmin = INF; double ymin = INF;
    double xmax = -INF; double ymax = -INF;
    for (i=1; i<=n; i++)
    {
        fin >> v[i].xx >> v[i].yy;
        xmin = min(xmin, v[i].xx); ymin = min(ymin, v[i].yy);
        xmax = max(xmax, v[i].xx); ymax = max(ymax, v[i].yy);
    }
    if (det(v[1], v[2], v[3]) > 0)
        for (i=2; i<=n/2+1; i++)
            swap(v[i], v[n-i+2]);
    p[1] = make_pair(xmin, ymin); p[2] = make_pair(xmax, ymin);
    p[3] = make_pair(xmax, ymax); p[4] = make_pair(xmin, ymax);
    v[n+1] = v[1]; int m = 4; p[5] = p[1];
    for (i=1; i<=n; i++)
    {
        /// intersectez i, i+1 cu j, j+1
        int k = 0; int ind = 0;
        for (j=1; j<=m; j++)
            if (det(v[i], v[i+1], p[j]) > 0)
            {
                ind = j;
                break;
            }
        j = ind;
        do {
            if (det(v[i], v[i+1], p[j]) == 0 && det(v[i], v[i+1], p[j+1]) == 0)
                aux[++k] = p[j+1];
            if (det(v[i], v[i+1], p[j]) == 0 && det(v[i], v[i+1], p[j+1]) > 0)
                aux[++k] = p[j+1];
            if (det(v[i], v[i+1], p[j]) > 0 && det(v[i], v[i+1], p[j+1]) == 0)
                aux[++k] = p[j+1];
            if (det(v[i], v[i+1], p[j]) < 0 && det(v[i], v[i+1], p[j+1]) == 0)
                aux[++k] = p[j+1];
            if (det(v[i], v[i+1], p[j]) > 0 && det(v[i], v[i+1], p[j+1]) > 0)
                aux[++k] = p[j+1];
            if (det(v[i], v[i+1], p[j]) > 0 && det(v[i], v[i+1], p[j+1]) < 0)
                aux[++k] = intersectDr(v[i], v[i+1], p[j], p[j+1]);
            if (det(v[i], v[i+1], p[j]) < 0 && det(v[i], v[i+1], p[j+1]) > 0)
            {
                aux[++k] = intersectDr(v[i], v[i+1], p[j], p[j+1]);
                aux[++k] = p[j+1];
            }
            j++;
            if (j == m+1)
                j = 1;
        } while (j != ind);
        aux[++k] = aux[1]; m = k-1;
        for (j=1; j<=k; j++)
            p[j] = aux[j];
    }
    double sol = 0;
    for (i=1; i<=m; i++)
        sol += det(origine, p[i], p[i+1]);
    if (sol < 0)
        sol = -sol;
    fout << setprecision(2) << fixed << sol/2.0;
    return 0;
}