Cod sursa(job #2382072)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 17 martie 2019 17:56:04
Problema Camera Scor 100
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 2.28 kb
#include <bits/stdc++.h>

#define cross(a,b) imag(conj(a)*b)

#define det(a,b,c) imag(conj(b-a)*(c-a))



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;

    nxt=(poz==n-1)?nxt=v[0]:nxt=v[poz+1];

    prv=(!poz)?prv=v.back():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(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();long double ans=0;

    for(int i=0,j=n-1;i<n;j=i++)

        ans+=(long double)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);
    v.clear();
    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;

}