Pagini recente » Cod sursa (job #2006956) | Cod sursa (job #862046) | Cod sursa (job #120114) | Cod sursa (job #1585953) | Cod sursa (job #1132968)
#include <cstdio>
#include <utility>
#include <algorithm>
#define N 120010
#define punct pair<double,double>
#define X first
#define Y second
using namespace std;
punct P[N],Q[N];
int n,i,p,u,crit(punct,punct);
double x,y,det(punct,punct,punct);
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%lf%lf",&x,&y);
P[i]=make_pair(x,y);
if(P[i]<P[0]){punct U=P[0];P[0]=P[i];P[i]=U;}
}
sort(P+1,P+n,crit);
Q[0]=P[0];Q[1]=P[1];p=0;u=1;
for(i=2;i<n;i++)
{
while(det(Q[p],Q[u],P[i])<0){p--;u--;}
p++;u++;Q[u]=P[i];
}
u++;
printf("%d\n",u);
for(i=0;i<u;i++)
printf("%.6lf %.6lf\n",Q[i].X,Q[i].Y);
return 0;
}
double det(punct A,punct B,punct C)
{
return A.X*B.Y+B.X*C.Y+C.X*A.Y-A.Y*B.X-B.Y*C.X-C.Y*A.X;
}
int crit(punct A,punct B)
{
double D=det(P[0],A,B);
if(D>0)return 1;
return 0;
}