Cod sursa(job #1279787)

Utilizator dr_personalityEftime Andrei Horatiu dr_personality Data 30 noiembrie 2014 21:27:52
Problema Aria Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include<fstream>
#include<iomanip>
using namespace std;
ifstream in("aria.in");
ofstream out("aria.out");
 
struct punct{
    double x, y;
};
 
const int nmax = 100006;
int srp[nmax], st[nmax], lst, n;
punct v[nmax];
 
int det(punct a, punct b, punct c)
{
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
 
double modul(double x)
{
    if(x<0)
        return -x;
    else
        return x;
}
 
double arie(punct v[], int n)
{
    if(n<3)
        return 0 ;
  
    st[0] = 1;
    st[1] = 2;
  
    for(int i = 0; i<nmax; i++)
        srp[i] = 0;
  
    int pozact = 2, lst = 1, pas = 1;
    double ar = 0;
  
    srp[2] = 1;
  
    while(srp[1]==0)
    {
        if(pozact==n)
            pas = -1;
  
        while(srp[pozact]==1)
            pozact += pas;
  
        while(lst!=0 && det(v[st[lst - 1]], v[st[lst]], v[pozact])>0)
            srp[st[lst--]] = 0 ;
  
        lst++;
        st[lst] = pozact;
        srp[pozact] = 1;
    }
  
    if(lst!=n)
        return 0;
  
    for(int i = 1; i<=lst; i++)
        ar += v[st[i - 1]].x * v[st[i]].y - v[st[i]].x * v[st[ i - 1 ]].y;
  
    return modul(ar);
}
 
int main(){
    int player_unu=0;
 
    in>>n;
    for(int i = 1; i<=n; i++)
        in>>v[i].x>>v[i].y;
 
    out<<setprecision(5)<<fixed;
    out<<arie(v, n) / 2;
 
    return player_unu;
}