Cod sursa(job #2507052)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 9 decembrie 2019 15:46:06
Problema Camera Scor 40
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 2.17 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define eps 0.000001
#define nmax 2005
#define xmax 1000000
using namespace std;
double ar;
struct point{double x;double y;};
point v[nmax],k[nmax*2],t[nmax*2];
int n,nrk,nrt;

double determinant(point a,point b,point c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
void ecuatiadreptei(point a,point b,double &a1,double &b1,double &c1)
{
    if (abs(a.x-b.x)<=eps) {
        a1=1;b1=0;c1=-a.x;
        return;
    }
    if (abs(a.y-b.y)<=eps) {
        a1=0;b1=1;c1=-a.y;
        return;
    }
    a1=b.y-a.y;
    b1=a.x-b.x;
    c1=a.y*(b.x-a.x)-a.x*(b.y-a.y);
}
point intersect(const point &a,const point &b,const point &c,const point &d)
{
    double a1,b1,c1,a2,b2,c2;
    ecuatiadreptei(a,b,a1,b1,c1);
    ecuatiadreptei(c,d,a2,b2,c2);
    point sol;
    sol.x=(c2*b1-c1*b2)/(a1*b2-a2*b1);
    if (b1)
        sol.y=(-c1-a1*sol.x)/b1;
    else
        sol.y=(-c2-a2*sol.x)/b2;
    return sol;
}
void dreapta(point a,point b)
{
    int i,ok=0;
    double d1;
    k[nrk+1]=k[1];
    for (i=1,nrt=0;i<=nrk;i++) {
        d1=determinant(k[i],a,b);
        if (d1<=eps)
            t[++nrt]=k[i];
        if (d1*determinant(k[i+1],a,b)<=eps)
            t[++nrt]=intersect(k[i],k[i+1],a,b);
    }
    for (i=1;i<=nrt;i++)
        k[i]=t[i];
    nrk=nrt;
}
void solve()
{
    int i;
    v[n+1]=v[1];
    nrk=4;
    k[1].x=-xmax;k[1].y=-xmax;
    k[2].x=xmax;k[2].y=-xmax;
    k[3].x=xmax;k[3].y=xmax;
    k[4].x=-xmax;k[4].y=xmax;
    for (i=1;i<=n;i++)
        dreapta(v[i],v[i+1]);
}
void aria()
{
    if (nrk==0) {
        for (int i=1;i<n/2;i++)
            swap(v[i],v[i+1]);
        solve();
    }
    k[nrk+1]=k[1];
    double sol=0;
    for (int i=1;i<=nrk;i++)
        sol+=determinant(k[0],k[i],k[i+1]);
    if (sol<0)
        sol=-sol;

    printf("%.2lf",(sol + 0.005) * 0.5);
}
int main()
{
    int i,x,y;
    freopen("camera.in","r",stdin);
    freopen("camera.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++) {
        scanf("%d %d",&x,&y);
        v[i].x=x;
        v[i].y=y;
    }
    solve();
    aria();
    return 0;
}