Cod sursa(job #1395571)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 21 martie 2015 12:26:07
Problema Aria Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("aria.in");
ofstream g("aria.out");

#include <algorithm>
#define x first
#define y second
#define mp make_pair
#define db double
#define LE 120666
#include <iomanip>
//#define cout g

pair<db,db> B[LE];
pair<db,db> Pmin;

db cross(pair<db,db> i1,pair<db,db> i2,pair<db,db> i3)
{
    i2.x-=i1.x,i3.x-=i1.x;
    i2.y-=i1.y,i3.y-=i1.y;
    return (i2.y*i3.x-i2.x*i3.y);
}

bool comp (pair<db,db> i1,pair<db,db> i2)
{
    db val=cross(Pmin,i1,i2);
    if (val==0) return i1.y>i2.y;
    return (val>0.0);
}

int solve(pair<db,db> A[],int N)
{
    Pmin=A[1];
    int i,ind_min=1;

    for(i=1; i<=N; ++i)
        if (A[i].y<Pmin.y)
            Pmin=A[i],ind_min=i;

    swap(A[ind_min],A[1]);
    sort(A+2,A+1+N,comp);

    int k=2;
    B[1]=A[1];
    B[2]=A[2];

    for(i=3; i<=N; ++i)
    {
        while (k>=2&&cross(B[k-1],B[k],A[i])<0.0) --k;
        B[++k]=A[i];
    }

    return k;
}

db Area(pair<db,db> A[],int N)
{
   db result=0;

   for(int i=1;i<N;++i)
     result+=cross(mp(0,0),A[i],A[i+1]);

    result+=cross(mp(0,0),A[N],A[1]);

    return (result<0.0?-result:result);
}

pair<db,db> V[LE];

int main()
{
    int n,i;

    f>>n;
    for(i=1; i<=n; ++i) f>>V[i].x>>V[i].y;
    db result=Area(V,n);
    result/=2.0;

    g<<fixed;
    g<<setprecision(6);
    g<<result<<'\n';

    return 0;
}