Cod sursa(job #943261)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 24 aprilie 2013 19:29:21
Problema Aria Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#define NMAX 100010

using namespace std;

struct punct
{
    int x, y;
}a[NMAX];

int n, ns, vz[NMAX],  S[NMAX];
long long sum;

void Citeste()
{
    int i;

    scanf("%d", &n);

    for (i=1; i<=n; ++i)
        scanf("%d", &a[i].x);

    for (i=1; i<=n; ++i)
        scanf("%d", &a[i].y);

}

inline int cmp(punct A, punct B)
{
    if (A.x<B.x || (A.x==B.x && A.y<B.y) ) return 1;
    return 0;
}

inline int determinant(punct A, punct B, punct C)
{
    return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}

void Infasoara()
{
    int i;

    S[1]=1;
    S[2]=2; vz[2]=1;
    ns=2;

    for (i=3; i<=n; ++i)
    {
        while (ns>1 && determinant(a[S[ns-1]], a[S[ns]], a[i])<0)
        {
            vz[S[ns]]=0; S[ns--]=0;
        }

        S[++ns]=i; vz[i]=1;
    }

    for (i=n; i>0; --i)
        if (!vz[i])
        {
            while (ns>1 && determinant(a[S[ns-1]], a[S[ns]], a[i])<0)
            {
                vz[S[ns]]=0; S[ns--]=0;
            }

            S[++ns]=i; vz[i]=1;
        }
}

void Aria()
{
    int i;
    long long A;

    for (i=2; i<ns-1; ++i)
    {
        A=abs(determinant(a[S[1]], a[S[i]], a[S[i+1]]));
        sum+=A;
    }

    if (sum%2==1)
    {
        sum/=2;
        printf("%d.50\n", sum);
    }
    else
    {
        sum/=2;
        printf("%d.00\n", sum);
    }
}

int main()
{
    freopen("aria.in", "r", stdin);
    freopen("aria.out", "w", stdout);

    Citeste();

    sort(a+1, a+n+1, cmp);

    Infasoara();

    Aria();

    return 0;
}