Pagini recente » Cod sursa (job #1482569) | Cod sursa (job #2945697) | Cod sursa (job #2804814) | Cod sursa (job #2416916) | Cod sursa (job #1279782)
#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;
}