Pagini recente » Cod sursa (job #1797692) | Cod sursa (job #1454959) | Cod sursa (job #1031011) | Cod sursa (job #369113) | Cod sursa (job #631662)
Cod sursa(job #631662)
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,i,l,w;
int s[120002],ap[120002];
struct vec
{
float x;
float y;
int p;
};
bool cmp(vec a,vec b)
{
if(a.y==b.y)
{
if(a.x<b.x) return 1;
else return 0;
}
else return a.y<b.y;
}
int det(float x1,float y1,float x2,float y2,float x3,float y3)
{
float s1;
s1=float((x1*y2)+(x2*y3)+(x3*y1)-(y2*x3)-(y3*x1)-(y1*x2));
if(s1>=0) return 0;
return 1;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
vec v[120002];
for(i=1;i<=n;i++)
{
scanf("%f",&v[i].x);
scanf("%f",&v[i].y);
}
for(i=1;i<=n;i++)
v[i].p=i;
sort(v+1,v+n+1,cmp);
l=1;
s[1]=v[1].p;
for(i=2;i<=n;i++)
{
if(l==1)
{
l++;
s[l]=v[i].p;
}
else
{
w=l-1;
while(det(v[s[w]].x,v[s[w]].y,v[s[w+1]].x,v[s[w+1]].y,v[i].x,v[i].y)==0&&w!=0) w--;
w=w+2;
l=w;
s[w]=v[i].p;
}
}
for(i=1;i<=l;i++)
ap[s[i]]=1;
for(i=1;i<=n;i++)
if(ap[i]==0)
{
if(l==1)
{
l++;
s[l]=v[i].p;
}
else
{
w=l-1;
while(det(v[s[w]].x,v[s[w]].y,v[s[w+1]].x,v[s[w+1]].y,v[i].x,v[i].y)==0&&w!=0) w--;
w=w+2;
l=w;
s[w]=v[i].p;
}
}
for(i=1;i<=l;i++)
{
printf("%.6f ",v[s[i]].x);
printf("%.6f\n",v[s[i]].y);
}
return 0;
}