Cod sursa(job #2339904)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 9 februarie 2019 15:20:39
Problema Camera Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 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;

void check(int poz)
{
    Point nxt,prv;
    if(poz==n-1)
       nxt=v[0];
    else
        nxt=v[poz+1];
    if(!poz)
        prv=v.back();
    else
        prv=v[poz-1];
    if(sgn(det(prv,v[poz],nxt))==1)
        reverse(u.begin(),u.end());
}

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(b,c,cur,prev));
        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;
    int topp=0;
    for(i=1;i<=n;i++)
    {
        double x,y;
        f>>x>>y;
        v.emplace_back(x,y);
        u.emplace_back(x,y);
        if(v[topp].imag()<v.back().imag())
            topp=i-1;
    }
    check(topp);
//    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;
}