Cod sursa(job #2507040)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 9 decembrie 2019 15:10:25
Problema Camera Scor 30
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 2.58 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define eps 0.000001
#define nmax 5005
#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;
    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;
}
double aria();

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]);

    double ans1 = aria();

    for (i = 1; i <= nrk; i++)
        k[i].x = 0, k[i].y = 0;
    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]);

    double ans2 = aria();

    printf("%.2lf", (max(ans1, ans2) + eps) * (0.5));
}
double 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;

    return sol;
}
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;
}