Cod sursa(job #2339921)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 9 februarie 2019 15:39:10
Problema Camera Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <bits/stdc++.h>

using namespace std;
using Point=complex<double>;
const double kEps=1e-9;

double cross(Point a,Point b){return imag(conj(a)*b);}
double det(Point a,Point b,Point c){return cross(b-a,c-a);}
int sgn(double d){return abs(d)<kEps?0:d>0?1:-1;}

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

int n,i,j;
vector<Point> v,u;

Point Intersection(Point a,Point b,Point p,Point q)
{
    double c1=det(a,b,p),c2=det(a,b,q);
    assert(abs(c1-c2)>kEps); // undefined if parallel
    return (c1*q-c2*p)/(c1-c2);
}


vector<Point> PolygonCut(const vector<Point>& P, Point s, Point e)
{
    if(P.empty())return P;
    vector<Point> res;int side1,side2;
    side2=sgn(det(s,e,P.back()));
    for(int i=0;i<(int)P.size();++i)
    {
        Point cur=P[i],prev=i?P[i-1]:P.back();
        side1=sgn(det(s,e,cur));
        if(side1*side2==-1)
            res.push_back(Intersection(s,e,cur,prev));
        if(side1>=0)res.push_back(cur);
        side2=side1;
    }
    return res;
}

double Area(vector<Point> P)
{
    int n=P.size();double ans=0;
    for(int i=0,j=n-1;i<n;j=i++)
        ans+=cross(P[j],P[i]);
    return abs(ans*.5);
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        double x,y;
        f>>x>>y;
        u.emplace_back(x,y);
    }
    if(Area(u)<-kEps)reverse(u.begin(),u.end());
    vector<Point> v={Point{-1e9,-1e9},Point{1e9,-1e9},Point{1e9, 1e9}, Point{-1e9, 1e9}};
//    for(auto it:v)
//        g<<real(it)<<' '<<imag(it)<<'\n';
    for(j=n-1,i=0;i<n;j=i++)
        v=PolygonCut(v,u[j],u[i]);
    g<<fixed<<setprecision(2)<<Area(v);
    return 0;
}