Pagini recente » Cod sursa (job #1850762) | Cod sursa (job #808143) | Cod sursa (job #2408597) | Cod sursa (job #2882093) | Cod sursa (job #600607)
Cod sursa(job #600607)
#include<stdio.h>
#include<algorithm>
using namespace std;
struct punct
{
double x,y;
};
punct a[120001];
int s[250000],n,lung,lung2,ss[250000];
bool cmp(punct a, punct b)
{
return a.x<b.x;
}
void scoate(int k)
{
while(lung>=2 && (a[k].y-a[s[lung]].y)*(a[k].x-a[s[lung-1]].x)<=(a[k].x-a[s[lung]].x)*(a[k].y-a[s[lung-1]].y))
--lung;
}
void adauga(int k)
{
s[++lung]=k;
}
int main()
{
int i;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
s[++lung]=1;
s[++lung]=2;
lung=2;
for(i=3;i<=n;++i)
{
scoate(i);
adauga(i);
}
for(i=1;i<lung;++i)
ss[i]=s[i];
lung2=lung;
lung = 0;
s[++lung]=n;
s[++lung]=n-1;
for(i=n-2;i>=1;--i)
{
scoate(i);
adauga(i);
}
printf("%d\n",lung+lung2-2);
for(i=1;i<lung2;++i)
printf("%.6lf %.6lf\n",a[ss[i]].x,a[ss[i]].y);
for(i=1;i<lung;++i)
printf("%.6lf %.6lf\n",a[s[i]].x,a[s[i]].y);
}