Cod sursa(job #3210148)

Utilizator DomnulMilandruMilandru Nicon-David DomnulMilandru Data 5 martie 2024 11:24:30
Problema Camera Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb

#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream cin("camera.in");
ofstream cout("camera.out");
int n;
vector<double> X;
vector<double> Y;
double arie;
const double M=100000;
double eps=1e-6;
vector<pair<double,double>> poligon;
double det(int a,int b,pair<double,double> p)
{
    return X[a]*Y[b]+X[b]*p.second+Y[a]*p.first-Y[b]*p.first-p.second*X[a]-X[b]*Y[a];
}
int semn(double a)
{
    if(-eps<a && a<eps)
       return 0;
    if(a>eps)
       return 1;
    return -1;
}
pair<double,double> intersectie (int a,int b,pair<double,double> c,pair<double,double> d)
{
    double a1=Y[a]-Y[b];
    double b1=X[b]-X[a];
    double c1=X[a]*Y[b]-Y[a]*X[b];

    double a2=c.second-d.second;
    double b2=d.first-c.first;
    double c2=c.first*d.second-c.second*d.first;

    double new_y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
    double new_x=(-c1-b1*new_y)/a1;
    return {new_x,new_y};
}
void determinare(int a,int b)
{
    vector<pair<double,double>> aux;
    poligon.push_back(poligon[0]);
    for(int i=0;i<poligon.size()-1;i++)
    {
        int semn1=semn(det(a,b,poligon[i]));
        int semn2=semn(det(a,b,poligon[i+1]));
        if(semn1*semn2==-1)
           aux.push_back(intersectie(a,b,poligon[i],poligon[i+1]));
        if(semn2>=0)
          aux.push_back(poligon[i+1]);
    }
    poligon=aux;
}
int main()
{
    cout<<setprecision(2)<<fixed;
    cin>>n;
    X.resize(n);
    Y.resize(n);
    for(int i=0;i<n;i++)
        cin>>X[i]>>Y[i];
    for(int i=0;i<n-1;i++)
        arie=arie+X[i]*Y[i+1]-Y[i]*X[i+1];
    arie=arie+X[n-1]*Y[0]-Y[n-1]*X[0];
    if(arie<0)
       {
           reverse(X.begin(),X.end());
           reverse(Y.begin(),Y.end());
       }
    arie=abs(arie)/2;
    poligon.push_back({-M,-M});
    poligon.push_back({M,-M});
    poligon.push_back({M,M});
    poligon.push_back({-M,M});
    for(int i=0;i<n-1;i++)
       determinare(i,i+1);
    determinare(n-1,0);
   if(poligon.size()==0)
      cout<<0;
    else
    {
        arie=0;
        for(int i=0;i<poligon.size()-1;i++)
           arie=arie+poligon[i].first*poligon[i+1].second-poligon[i].second*poligon[i+1].first;
        arie=arie+poligon[poligon.size()-1].first*poligon[0].second-poligon[poligon.size()-1].second*poligon[0].first;
        arie=abs(arie)/2;
        cout<<arie;
    }
    return 0;
}