Cod sursa(job #2466281)

Utilizator Carol_LucaCarol Luca Carol_Luca Data 1 octombrie 2019 20:31:23
Problema Camera Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 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;



}