Pagini recente » Cod sursa (job #431762) | Cod sursa (job #1117408) | Cod sursa (job #2675362) | Cod sursa (job #2532162) | Cod sursa (job #1319065)
#include <stdio.h>
#include <algorithm>
using namespace std;
struct cel
{
double x,y;
}a[120005];
bool cmp(cel p1,cel p2)
{
return (p1.y-a[1].y)*(p2.x-a[1].x)<(p2.y-a[1].y)*(p1.x-a[1].x);
}
int lista[120005];
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n;
scanf("%d",&n);
double minimx=2000000000,minimy=2000000000;
int pos=0;
for (int i=1;i<=n;++i)
{
scanf("%lf %lf",&a[i].x,&a[i].y);
if (a[i].y<minimy || (a[i].y==minimy && a[i].x<minimx))
{
pos=i;
minimx=a[i].x;
minimy=a[i].y;
}
}
double t=a[1].x; a[1].x=a[pos].x; a[pos].x=t;
t=a[1].y; a[1].y=a[pos].y; a[pos].y=t;
sort(a+2,a+1+n,cmp);
int num=2;
lista[1]=1; lista[2]=2;
int i=3;
while (i<=n)
{
cel p1=a[lista[num-1]],p2=a[lista[num]],p3=a[i];
while (num>=2 && (p3.y-p1.y)*(p2.x-p1.x)-(p2.y-p1.y)*(p3.x-p1.x)<0)
{
--num;
p1=a[lista[num-1]]; p2=a[lista[num]];
}
++num;
lista[num]=i;
++i;
}
printf("%d\n",num);
for (int i=1;i<=num;++i)
{
printf("%.12lf %.12lf\n",a[lista[i]].x,a[lista[i]].y);
}
fclose(stdin);
fclose(stdout);
return 0;
}