Cod sursa(job #2339916)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 9 februarie 2019 15:34:42
Problema Camera Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 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);
//    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;
}