Pagini recente » Cod sursa (job #1638822) | Cod sursa (job #2428320) | Cod sursa (job #1627529) | Cod sursa (job #2638357) | Cod sursa (job #1821003)
#include <iostream>
#define e 0.000000000001
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
double lst[120004][2],n,t;
int stp =-1 ,stk[120004];
double det(int a,int b,int c)
{
return (lst[b][0]-lst[a][0])*(lst[c][1]-lst[a][1])-(lst[c][0]-lst[a][0])*(lst[b][1]-lst[a][1]);
}
bool cmp ( int a , int b )
{
return det(0,a,b) < 0;
}
int main()
{
cin>>n;
for(int i=0; i<n; i++)
cin>>lst[i][0]>>lst[i][1];
for(int i=0; i<n; i++)
if(lst[i][1] < lst[stp][1] || stp == -1)
stp = i;
else if(fabs(lst[i][1]-lst[stp][1]<e))
if(lst[i][0]-lst[stp][0]<0)
stp=i;
t=lst[stp][0];
lst[stp][0]=lst[0][0];
lst[0][0] = t ;
t=lst[stp][1];
lst[stp][1]=lst[0][1];
lst[0][1] = t ;
///sort( lst +1 , lst + n , cmp );
for(int i=1; i<n-1; i++)
for(int j=i+1; j<n; j++)
if(det(0,i,j)>0)
{
t=lst[i][0];
lst[i][0]=lst[j][0];
lst[j][0] = t ;
t=lst[i][1];
lst[i][1]=lst[j][1];
lst[j][1] = t ;
}
stk[0] = 0;
stk[1] = 1;
int sp = 1;
for (int i = 2 ; i <n ; i++ )
{
while(sp>=1 && det(stk[sp-1],stk[sp],i)>0.0)
sp--;
stk[++sp] = i;
}
printf("%d\n",sp+1);
for (int i = sp ; i >=0 ; i-- )
printf("%lf %lf\n",lst[stk[i]][0] , lst[stk[i]][1]);
return 0;
}