Pagini recente » Cod sursa (job #1009690) | Cod sursa (job #1698299) | Cod sursa (job #1163200) | Cod sursa (job #2186361) | Cod sursa (job #2883372)
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<iostream>
#define MAX 1000000000
using namespace std;
struct punct
{
double x,y;
int parte;
}v[120005];
int st[120005];
double arie(punct a, punct b, punct c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
}
bool cmp(punct a, punct b)
{
if(a.y<b.y)
return true;
else
if(a.y>b.y)
return false;
else
return (a.x<b.x);
}
int main()
{
double maxx=0, maxy=0, minx=MAX+MAX+100, miny=MAX+MAX+100;
int poz,i,n,pozmin,pozmax;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%lf%lf",&v[i].x,&v[i].y);
if(miny>v[i].y)
{
pozmin=i;
minx=v[i].x;
miny=v[i].y;
}
else
if(miny==v[i].y)
if(v[i].x<minx)
{
pozmin=i;
minx=v[i].x;
miny=v[i].y;
}
if(maxy<v[i].y)
{
pozmax=i;
maxx=v[i].x;
maxy=v[i].y;
}
else
if(maxy==v[i].y)
if(v[i].x<minx)
{
pozmax=i;
maxx=v[i].x;
maxy=v[i].y;
}
}
for(i=1; i<=n; i++)
if(i!=pozmin&&i!=pozmax)
if(arie(v[pozmin],v[pozmax],v[i])<0)
v[i].parte=1;
else
v[i].parte=-1;
sort(v+1,v+n+1,cmp);
pozmin=1;
pozmax=n;
for(i=1; i<=n; i++)
if(i!=pozmin&&i!=pozmax)
if(arie(v[pozmin],v[pozmax],v[i])<0)
v[i].parte=1;
else
v[i].parte=-1;
int k;
v[1].parte=-1;
v[n].parte=1;
st[1]=1;
i=2;
while(v[i].parte==-1&&i<n)
i++;
st[2]=i;
k=2;
int p;
double a;
p=v[st[2]].parte;
for(i=i+1; i<=n; i++)
if(v[i].parte==p)
{
a=arie(v[st[k-1]],v[st[k]],v[i]);
while(a*v[i].parte<0&&k>0)
{
k--;
a=arie(v[st[k-1]],v[st[k]],v[i]);
}
k++;
st[k]=i;
}
/*a=arie(v[st[k-1]],v[st[k]],v[n]);
while(a*v[n].parte<=0&&k>0){
k--;
a=arie(v[st[k-1]],v[st[k]],v[n]);
}
st[++k]=n;*/
i=n-1;
p=-1;
while(v[i].parte==1&&i>1)
i--;
k++;
st[k]=i;
for(i=i-1; i>=2; i--)
if(v[i].parte==p)
{
a=arie(v[st[k-1]],v[st[k]],v[i]);
while(a*v[i].parte>0&&k>0)
{
k--;
a=arie(v[st[k-1]],v[st[k]],v[i]);
}
k++;
st[k]=i;
}
a=arie(v[st[k-1]],v[st[k]],v[1]);
while(a*v[1].parte>0&&k>0)
{
k--;
a=arie(v[st[k-1]],v[st[k]],v[1]);
}
printf("%d\n",k);
for(i=1; i<=k; i++)
cout<<fixed<<setprecision(6)<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
///printf("%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
return 0;
}