Pagini recente » Cod sursa (job #2118106) | Cod sursa (job #751662) | Cod sursa (job #2310775) | Cod sursa (job #1863424) | Cod sursa (job #2372673)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int st[120010],n,m,k,viz[120010];
struct punct{
long double x,y;
}a[120010];
bool cmp(punct A,punct B){
return A.x<B.x||(A.x==B.x&&A.y<B.y);
}
bool valid(int i,int j,int k){
return(a[i].x*a[j].y+a[i].y*a[k].x+a[j].x*a[k].y-a[j].y*a[k].x-a[k].y*a[i].x-a[i].y*a[j].x)<0;
}
int main()
{
f>>n;
for(int i=1;i<=n;++i){
f>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1,cmp);
st[1]=1;
st[2]=2;
viz[2]=1;
k=2;
for(int i=3;i<=n;++i){
while(k>=2&&!valid(st[k-1],st[k],i))viz[st[k--]]=0;;
st[++k]=i;
viz[i]=1;
}
for(int i=n;i>=1;--i){
if(viz[i]) continue;
while(k>=2&&!valid(st[k-1],st[k],i))viz[st[k--]]=0;;
st[++k]=i;
viz[i]=1;
}
g<<k-1<<'\n';
for(int i=k-1;i>=1;--i){
g<<fixed<<setprecision(6)<<a[st[i]].x<<" "<<a[st[i]].y<<'\n';
}
}