Pagini recente » Cod sursa (job #2922659) | Statistici Sirbu Lavinia Stefania 323CC (Sirbu_Lavinia_Stefania_323CC) | Cod sursa (job #1845872) | Cod sursa (job #1373005) | Cod sursa (job #2067579)
#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);
v[i].x+=MAX;
v[i].y+=MAX;
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);
int k;
st[1]=1;
i=2;
while(v[i].parte==-1)
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]);
if(a*v[i].parte<0)
st[k]=i;
else
st[++k]=i;
}
st[++k]=n;
i=n-1;
p=-1;
while(v[i].parte==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]);
if(a*v[i].parte>0)
st[k]=i;
else
st[++k]=i;
}
printf("%d\n",k);
for(i=1;i<=k;i++)
cout<<fixed<<setprecision(6)<<v[st[i]].x-MAX<<" "<<v[st[i]].y-MAX<<'\n';
//printf("%.6lf %.6lf\n",v[st[i]].x-MAX,v[st[i]].y-MAX);
return 0;
}