Cod sursa(job #1279782)

Utilizator dr_personalityEftime Andrei Horatiu dr_personality Data 30 noiembrie 2014 21:20:13
Problema Aria Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 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);
}

int modul(int x)
{
	if(x<0)
		return -x;
	else
		return x;
}

int 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;
}