Cod sursa(job #2979665)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 15 februarie 2023 18:27:02
Problema Camera Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

#define pii pair <long long, long long>
#define ll long long

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

struct str
{
    double x, y;
};

const long long max_size = 2e3 + 3;
const double eps = 1e-7, INF = 1e5 + 1;

str v[max_size];
vector <str> plan, aux;

double arie (str x, str y, str z)
{
    return (x.x * (y.y - z.y) + y.x * (z.y - x.y) + z.x * (x.y - y.y));
}

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

void push (str y1, str y2, str x1, str x2)
{
    double difxx = x1.x - x2.x, difxy = x2.y - x1.y, difyx = y1.x - y2.x, difyy = y2.y - y1.y;
    double aux1 = (x2.x * x1.y - x1.x * x2.y), aux2 = (y2.x * y1.y - y1.x * y2.y);
    double x = (aux2 * difxx - aux1 * difyx) / (difxy * difyx - difxx * difyy), y = (aux1 * difyy - aux2 * difxy) / (difxy * difyx - difxx * difyy);
    aux.push_back({x, y});
}

signed main ()
{
    long long n;
    double arietot = 0;
    in >> n;
    for (long long i = 1; i <= n; i++)
    {
        in >> v[i].x >> v[i].y;
    }
    for (int i = 1; i < n; i++)
    {
        arietot += arie(v[i], v[i + 1], {0, 0});
    }
    if (arietot < 0)
    {
        reverse(v + 1, v + n  + 1);
    }
    v[n + 1] = v[1];
    plan.push_back({-INF, -INF});
    plan.push_back({INF, -INF});
    plan.push_back({INF, INF});
    plan.push_back({-INF, INF});
    for (long long i = 1; i <= n; i++)
    {
        for (long long j = 0; j < plan.size(); j++)
        {
            long long k = j + 1;
            if (k == plan.size())
            {
                k = 0;
            }
            long long sgn1 = sgn(arie(v[i], v[i + 1], plan[j])), sgn2 = sgn(arie(v[i], v[i + 1], plan[k]));
            if (sgn1 * sgn2 == -1)
            {
                push(plan[j], plan[k], v[i], v[i + 1]);
            }
            if (sgn2 >= 0)
            {
                aux.push_back(plan[k]);
            }
        }
        plan = aux;
        aux.clear();
    }
    double ans = 0;
    for (long long i = 0; i < plan.size(); i++)
    {
        //out << plan[i].x << " " << plan[i].y << '\n';
        long long j = i + 1;
        if (j == plan.size())
        {
            j = 0;
        }
        ans += arie(plan[i], plan[j], {0, 0});
    }
    if (ans < 0)
    {
        ans = -ans;
    }
    ans /= 2;
    out << fixed << setprecision(2) << ans;
    in.close();
    out.close();
    return 0;
}