Cod sursa(job #2885894)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 6 aprilie 2022 18:55:55
Problema Camera Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

const string filename = "camera";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

const int maxN = 2005;
const long double eps = 1e-7;
int n;
struct point {
    double cx, cy;
}pct[maxN], ans;
vector <point> varf, aux;


double arie(point a, point b, point c)
{
    /// ax ay 1 )
    /// bx by 1  ) => d = ax * by + ay * cx + bx * cy - by * cx - ay * bx - ax * cy
    /// cx cy 1 )
    return a.cx * b.cy + a.cy * c.cx + b.cx * c.cy - b.cy * c.cx - a.cy * b.cx - a.cx * c.cy;
}

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

void add(point y1, point y2, point x1, point x2)
{
    double dxx, dxy, dyx, dyy, xc, yc, x, y;
    dxx = x1.cx - x2.cx, dxy = x2.cy - x1.cy;
    dyx = y1.cx - y2.cx, dyy = y2.cy - y1.cy;
    xc = (x2.cx * x1.cy - x1.cx * x2.cy);
    yc = (y2.cx * y1.cy - y1.cx * y2.cy);
    x = (yc * dxx - xc * dyx) / (dxy * dyx - dxx * dyy);
    y = (xc * dyy - yc * dxy) / (dxy * dyx - dxx * dyy);
    //cout << x1.cx << ' ' << x1.cy << "   " << x2.cx << ' ' << x2.cy << "   " << y1.cx << ' ' << y1.cy << "   " << y2.cx << ' ' << y2.cy << "   " << x << ' ' << y << '\n';
    aux.push_back({x, y});
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> pct[i].cx >> pct[i].cy;
    double x = 0;
    for(int i = 1; i < n; i++)
        x += arie(pct[i], pct[i + 1], {0, 0});
    if(x < 0)
        reverse(pct + 1, pct + n + 1);
    pct[++n] = pct[1];
    varf.push_back({-1e5, -1e5});
    varf.push_back({1e5, -1e5});
    varf.push_back({1e5, 1e5});
    varf.push_back({-1e5, 1e5});
    for(int i = 1; i < n; i++)
    {
        //cout << i << ":\n";
        //for(auto elem : varf)
        //    cout << elem.cx << ' ' << elem.cy << "   ";
        for(int j = 0; j < (int)varf.size(); j++)
        {
            int nxt = j + 1, semn1, semn2;
            if(nxt >= varf.size())
                nxt -= varf.size();
            semn1 = get_semn(arie(pct[i], pct[i + 1], varf[j]));
            semn2 = get_semn(arie(pct[i], pct[i + 1], varf[nxt]));
            //cout << pct[i].cx << ' ' << pct[i].cy << "   " << pct[i + 1].cx << ' ' << pct[i + 1].cy << "   " << varf[j].cx << ' ' << varf[j].cy << "   " << varf[nxt].cx << ' ' << varf[nxt].cy << "      " << semn1 << ' ' << semn2 << '\n';
            if(semn1 * semn2 <= 0)
                add(varf[j], varf[nxt], pct[i], pct[i + 1]);
            if(semn2 >= 0)
                aux.push_back(varf[nxt]);
        }
        varf = aux;
        //cout << '\n';
        aux.clear();
    }
    if(varf.empty())
    {
        fout << 0;
        return 0;
    }
    double total_arie = 0;
    for(int i = 0; i < (int)varf.size();i++)
    {
        int nxt = (i + 1) % varf.size();
        total_arie += arie(varf[i], varf[nxt], {0,0});
    }
    if(total_arie < 0)
        total_arie = -total_arie;
    total_arie /= 2;
    fout << fixed << setprecision(2) << total_arie;
    return 0;
}