Pagini recente » Cod sursa (job #433719) | Cod sursa (job #811247) | Profil Tiberiur | Cod sursa (job #1086089) | Cod sursa (job #883376)
Cod sursa(job #883376)
#include<stdio.h>
#include<algorithm>
#define x first
#define y second
using namespace std;
pair<double , double> a[120007],st[120007];
int n;
inline double cp( pair<double , double> A , pair<double , double> B , pair<double , double> C)
{
return (B.x-A.x)*(C.y-B.y)-(B.y-A.y)*(C.x-B.x);
}
inline int cmp(pair<double , double> p1,pair<double , double> p2)
{
return cp(a[1] , p1 , p2) < 0;
}
int infasuratoare()
{
int poz=1;
for (int i=2 ; i<=n ; ++i)
if (a[i] < a[poz])
poz=i;
swap(a[1] , a[poz]);
sort(a+2 , a+n+1 , cmp);
//sort(a+1 , a+n+1 , cmp);
st[1]=a[1];
st[2]=a[2];
int nr=2;
for (int i=3 ; i<=n ; ++i)
{
while(nr>=3&&cp(st[nr-1] , st[nr] , a[i]) > 0)
--nr;
st[++nr]=a[i];
}
return nr;
}
int main()
{
freopen("infasuratoare.in" , "r" , stdin);
freopen("infasuratoare.out" , "w" , stdout);
scanf("%d\n" , &n);
for (int i=1 ; i<=n ; ++i)
scanf("%lf %lf" , &a[i].x , &a[i].y);
n=infasuratoare();
printf("%d\n" , n);
for (int i=n ; i>=1 ; --i)
printf("%.6lf %.6lf\n" , st[i].x , st[i].y);
return 0;
}