Cod sursa(job #2339871)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 9 februarie 2019 14:43:48
Problema Camera Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 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(vector<Point>& a,Point b,Point c)
{
    vector<Point> ret;
    for(int i=0,j=a.size()-1;i<a.size();j=i++)
    {
        Point prev=a[j],cur=a[i];
        int side1=sgn(det(b,c,cur));
        int side2=sgn(det(b,c,prev));
        if(side1*side2==-1)
            ret.push_back(Intersection(prev,cur,b,c));
        if(side1<=0)
            ret.push_back(cur);
    }
    return ret;
}

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;
        v.emplace_back(x,y);
        u.emplace_back(x,y);
    }
    for(j=n-1,i=0;i<n;j=i++)
        v=PolygonCut(v,u[j],u[i]);
//    for(auto it:v)
//        g<<real(it)<<' '<<imag(it)<<'\n';
    g<<fixed<<setprecision(7)<<Area(v);
    return 0;
}