Pagini recente » Cod sursa (job #970490) | Cod sursa (job #652282) | Cod sursa (job #1916433) | Cod sursa (job #2593386) | Cod sursa (job #1919174)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const double eps=0.000000000001;
struct punct{double x,y;}v[120005];
int n,i,j,st[120005],top,step;
bool viz[120005];
inline bool cmp (punct A,punct B)
{if(A.x==B.x)return A.y<B.y;
else return A.x<B.x;
}
inline bool Det(punct A,punct B, punct C)
{return C.x*(A.y-B.y)+C.y*(B.x-A.x)+A.x*B.y-A.y*B.x<=eps;
}
int main()
{fin>>n;
for(i=1;i<=n;i++)
{fin>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,cmp);
st[1]=1;
st[2]=2;
top=2;
step=1;
viz[2]=1;
for(i=3;i;i+=step)
{if(viz[i]==1)continue;
while(top>=2&&Det(v[st[top-1]],v[st[top]],v[i]))
{viz[st[top]]=0;
top--;
}
top++;
st[top]=i;
viz[i]=1;
if(i==n)step=-1;
}
top--;
fout<<top<<"\n";
for(i=1;i<=top;i++)
{
fout<<setprecision(12)<<fixed;
fout<<v[st[i]].x<<" ";
fout<<setprecision(12)<<fixed;
fout<<v[st[i]].y<<"\n";
}
}