Pagini recente » Cod sursa (job #212868) | Cod sursa (job #1018594) | Cod sursa (job #1518255) | Cod sursa (job #1638630) | Cod sursa (job #2952204)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
int i,n,l;
struct punct{
double x, y;
};
bool semn(punct a, punct b, punct o)
{
return (a.x-o.x)*(b.y-o.y)<(a.y-o.y)*(b.x-o.x);
}
punct v[150000], st[150000], o ;
int det(punct p1, punct p2, punct p3){
return (p1.x*p2.y+p1.y*p3.x+p2.x*p3.y- p2.y*p3.x-p1.y*p2.x-p3.y*p1.x)<0;
}
bool comp(punct a, punct b){
return semn(a, b, v[1]);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
cin>>n;
int pos=1;
for(int i=1;i<=n;i++){
cin>>v[i].x>>v[i].y;
if(v[i].x<v[pos].x|| (v[i].x==v[pos].x && v[i].y<v[pos].y))
pos=i;
}
swap(v[1], v[pos]);
sort(v+2, v+n+1, comp);
st[1]=v[1];
st[2]=v[2];
l= 2;
for(int i=3;i<=n;i++)
{
while(l>=2 &&!semn(st[l], v[i], st[l-1]))
{
l--;
}
st[++l]= v[i];
}
cout<<l<<endl;
cout<<fixed<<setprecision(6)<<st[1].x<<" "<<st[1].y<<endl;
for(int i=l;i>=2;i--)
{
cout<<fixed<<setprecision(6)<<st[i].x<< " "<<st[i].y<<endl;
}
}