Pagini recente » Cod sursa (job #3340963) | Cod sursa (job #2943641) | Cod sursa (job #1328447) | Cod sursa (job #1927490) | Cod sursa (job #3353326)
/*
* author [dubit]
*/
#include <bits/stdc++.h>
using namespace std;
struct point{
double x,y;
};
point origin={0,0};
double det(point a,point b,point c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double dist(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(point a,point b)
{
double d=det(origin,a,b);
if(d)
return d>0;
return dist(origin,a)>dist(origin,b);
}
point v[120005];
int n,minimizedpoint;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
cin>>n;
v[0]={1000000005,1000000005};
for(int i=1;i<=n;i++)
{
cin>>v[i].x>>v[i].y;
if(v[i].y<v[minimizedpoint].y
|| (v[i].y==v[minimizedpoint].y && v[i].x<v[minimizedpoint].x) )
minimizedpoint=i;
}
v[0]=v[minimizedpoint];
swap(v[minimizedpoint],v[1]);
origin=v[1];
sort(v+2,v+n+1,cmp);
int firstDetNotEqualToZero;
for(firstDetNotEqualToZero=2;firstDetNotEqualToZero<=n;firstDetNotEqualToZero++)
if(det(v[1],v[2],v[firstDetNotEqualToZero]))
break;
for(int i=2, j=firstDetNotEqualToZero-1;i<j;i++,j--)
swap(v[i],v[j]);
point stk[120005];
int top=2;
stk[1]=v[1];
stk[2]=v[2];
for(int i=3;i<=n;i++)
{
while(top>=2 && det(stk[top-1],stk[top],v[i])<0)
top--;
stk[++top]=v[i];
}
cout<<top<<'\n';
for(int i=1;i<=top;i++)
cout<<fixed<<setprecision(6)<<stk[i].x<<' '<<stk[i].y<<'\n';
return 0;
}