Cod sursa(job #3203670)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 14 februarie 2024 09:53:56
Problema Camera Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;

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

const double eps = 1e-6;

int n;
const int nmax = 2000;

struct point{
double x;
double y;
}v[nmax + 5],mn,mx;
struct general_equation{
double a;
double b;
double c;
    general_equation(point p1,point p2)
    {
        a = p1.y-p2.y;
        b = p2.x-p1.x;
        c = (p1.x-p2.x)*p1.y + (p2.y-p1.y)*p1.x;
    }


};



/*
ax ay 1
bx by 1
cx cy 1

bx-ax)(cy-ay) - (cx-ax)(by-ay) */

double det(point a,point b,point c)
{
    return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
void check()
{
    double sol = 0.0;
    for(int i = 1;i<=n;i++)
        sol+=v[i].x * v[i+1].y - v[i+1].x * v[i].y;
    if(sol>=-eps){
        for(int i = 1;i<=n/2;i++)
            swap(v[i],v[n-i+1]);
        v[n+1]=v[1];
    }
}

bool outside(point a,point b,point c)
{
    return det(a,b,c)>0;
}
bool inside(point a,point b,point c)
{
    return det(a,b,c)<=eps;
}

point intersection(general_equation l1,general_equation l2)
{
    point sol={0,0};
    sol.x = (l2.c * l1.b - l1.c * l2.b)/(l1.a*l2.b-l2.a*l1.b);
    sol.y = (l2.a*l1.c - l1.a * l2.c )/(l1.a*l2.b -l2.a*l1.b);
    return sol;
}


void solve()
{
    mn={100005,100005};
    mx={-100005,-100005};
    for(int i=1;i<=n;i++){
        double x,y;
        fin>>x>>y;
        v[i]={x,y};
        mn.x=min(x,mn.x);
        mn.y=min(y,mn.y);
        mx.x=max(x,mx.x);
        mx.y=max(y,mx.y);
    }
    v[n+1]=v[1];
    check();
    vector <point> poly;
    poly.push_back(mn);
    poly.push_back({mx.x,mn.y});
    poly.push_back(mx);
    poly.push_back({mn.x,mx.y});
    poly.push_back(mn);


    for(int i=1;i<=n;i++)
    {
        point a = v[i];
        point b = v[i+1];
        vector<point> poly_aux;
        for(int j = 1;j<poly.size();j++)
        {
            point nxt = poly[j];
            point crt = poly[j-1];

            if(inside(a,b,nxt) && inside(a,b,crt))
                poly_aux.push_back(nxt);
            else if (inside(a,b,crt) && outside(a,b,nxt))
                poly_aux.push_back(intersection(general_equation(a,b),general_equation(crt,nxt)));
            else if (outside(a,b,crt) && inside(a,b,nxt))
            {
                poly_aux.push_back(intersection(general_equation(a,b),general_equation(crt,nxt)));
                poly_aux.push_back(nxt);
            }
        }

        poly.clear();
        for(auto& i : poly_aux)
            poly.push_back(i);
        poly.push_back(poly.front());

        //fout<<poly.size()<<'\n';
    }
    /*for(auto& i : poly)
    {
        fout<<i.x<<' '<<i.y<<'\n';
    }*/
    double sol = 0.0;
    for(int i = 0;i+1<poly.size();i++)
        sol+=poly[i].x * poly[i+1].y - poly[i+1].x * poly[i].y;
    sol/=2;
    if(sol<0)
        sol=-sol;
    fout<<fixed<<setprecision(3)<<sol;
}

int main()
{
    fin>>n;
    solve();
}