Pagini recente » Cod sursa (job #2772795) | Cod sursa (job #2195256) | Cod sursa (job #2981209) | Cod sursa (job #2924334) | Cod sursa (job #236127)
Cod sursa(job #236127)
#include<stdio.h>
#include<algorithm>
#include<vector>
#define mkp make_pair
#define pb push_back
using namespace std;
const int maxn = 1200000;
vector<pair<double,double> > VECT;
double ARIE;
int N,ST[maxn],VER[maxn];
//Semnul verifica ca triunghiul dat este parcurs in ordine invers trigonometrica
double semn(int i1,int i2,int i3)
{
return VECT[i1].first * VECT[i2].second + VECT[i2].first * VECT[i3].second + VECT[i3].first * VECT[i1].second - VECT[i1].second * VECT[i2].first - VECT[i2].second * VECT[i3].first - VECT[i3].second * VECT[i1].first;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&N);
for(int i = 1; i <= N; ++i)
{
double x = 0,y = 0;
scanf("%lf %lf\n",&x,&y);
VECT.pb(mkp(x,y));
}
//Verific sa fie sortat
reverse(VECT.begin(),VECT.end());
if (next_permutation(VECT.begin(),VECT.end())) sort(VECT.begin(),VECT.end());
else reverse(VECT.begin(),VECT.end());
ST[ST[0] = 1] = 1;
// Prima data cand fac stiva pentru partea din dreapta dreptei (Pjos,Psus)
for(int i = 2;i <= N; ++i)
{
if (VER[i]) continue;
while(ST[0] >= 2 && semn(ST[ST[0] - 1] - 1,ST[ST[0]] - 1,i - 1) > 0)
{
VER[ST[ST[0]]] = 0;
ST[0]--;
}
ST[++ST[0]] = i;
VER[i] = 1;
}
// A 2-a oara cand fac stiva pentru partea din stanga dreptei (Pjos,Psus)
for(int i = N;i; --i)
{
if (VER[i]) continue;
while(ST[0] >= 2 && semn(ST[ST[0] - 1] - 1,ST[ST[0]] - 1,i - 1) > 0){VER[ST[ST[0]]] = 0;ST[0]--;}
ST[++ST[0]] = i;
VER[i] = 1;
}
//Aria se calculeaza cu determinant
for(int i = 2;i <= ST[0]; ++i)
ARIE += VECT[ST[i - 1] - 1].first * VECT[ST[i] - 1].second - VECT[ST[i - 1] - 1].second * VECT[ST[i] - 1].first;
ARIE = ARIE > 0 ? ARIE : -ARIE;
printf("%.4lf\n",ARIE / 2);
return 0;
}