Cod sursa(job #2098582)

Utilizator refugiatBoni Daniel Stefan refugiat Data 3 ianuarie 2018 09:11:05
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <bits/stdc++.h>
#define NMAX 2005
#define LIM 100000
#define EPS 1e-6
using namespace std;
ifstream si("camera.in");
ofstream so("camera.out");
struct pct{
    long double x,y;
    pct(){}
    pct(long double nx,long double ny) {
        x=nx;
        y=ny;
    }
};
struct dr{
    long double a,b,c;
    dr(pct p1,pct p2) {
        a=p2.y-p1.y;
        b=p1.x-p2.x;
        c=p1.y*p2.x-p1.x*p2.y;
    }
};
vector<pct> a,v,nv;
inline long double det(pct a,pct b,pct c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-(a.x*c.y+b.x*a.y+c.x*b.y);
}
inline long double arie(vector<pct> a)
{
    long double ans=det(a.back(),a.front(),pct(0,0));
    for(int i=0;i<a.size()-1;++i)
    {
        ans+=det(a[i],a[i+1],pct(0,0));
    }
    return ans;
}
inline pct inter(dr d1,dr d2)
{
    long double x,y;
    x=(d2.c*d1.b-d1.c*d2.b)/(d1.a*d2.b-d2.a*d1.b);
    y=(d1.c*d2.a-d2.c*d1.a)/(d1.a*d2.b-d2.a*d1.b);
    return pct(x,y);
}
inline int semn(long double x)
{
    if(x<EPS&&x>-EPS) return 0;
    if(x>EPS) return 1;
    return -1;
}
void solve(pct a,pct b)
{
    int n=v.size();
    dr d(a,b);
    v.push_back(v[0]);
    nv.clear();
    int s1,s2;
    pct p;
    for(int i=0;i<n;++i)
    {
        s1=semn(det(a,b,v[i]));
        s2=semn(det(a,b,v[i+1]));
        p=inter(dr(v[i],v[i+1]),d);
        if(s1*s2==-1)
            nv.push_back(p);
        if(s2>=0)
            nv.push_back(v[i+1]);
    }
    v=nv;
}
int main()
{
    int n;
    si>>n;
    a.resize(n);
    for(int i=0;i<n;++i)
        si>>a[i].x>>a[i].y;
    if(arie(a)<0)
        reverse(a.begin(),a.end());
    a.push_back(a[0]);
    v.push_back({-LIM,-LIM});
    v.push_back({LIM,-LIM});
    v.push_back({LIM,LIM});
    v.push_back({-LIM,LIM});
    for(int i=0;i<n&&!v.empty();++i)
        solve(a[i],a[i+1]);
    if(v.empty())
    {
        so<<0<<'\n';
        return 0;
    }
    long double s=arie(v);
    if(s<0)
        s=-s;
    s/=2;
    so<<setprecision(2)<<fixed<<s<<'\n';
    return 0;
}