Pagini recente » Cod sursa (job #1734095) | Cod sursa (job #488006) | Cod sursa (job #2222943) | Cod sursa (job #2742235) | Cod sursa (job #2044418)
#include <bits/stdc++.h>
using namespace std;
struct punct{
double x,y;
}a[120005];
int n,st[120005],top;
bool viz[120005];
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
inline bool cmp(punct A,punct B)
{
if (A.y==B.y) return A.x<B.x;
else return A.y<B.y;
}
inline double F(int i,int j,int p)
{
return a[p].x*(a[i].y-a[j].y)+a[p].y*(a[j].x-a[i].x)+a[i].x*a[j].y-a[j].x*a[i].y;
}
void Hill()
{
int i;
punct p;
sort(a+1,a+n+1,cmp);
st[++top]=1;
st[++top]=2;
viz[1]=viz[2]=1;
for (i=3;i<=n;++i)
{
p=a[i];
while (top>=2 && F(st[top-1],st[top],i)<0) {
viz[st[top]]=0;
--top;
}
st[++top]=i;
viz[i]=1;
}
for (i=n-1;i>=1;--i)
if (!viz[i])
{
while (F(st[top-1],st[top],i)<0)
{
viz[st[top]]=0;
--top;
}
st[++top]=i;
viz[i]=1;
}
while (F(st[top-1],st[top],1)<0) --top;
}
int main()
{
int i;
fin>>n;
for (i=1;i<=n;++i)
fin>>a[i].x>>a[i].y;
Hill();
fout<<top<<'\n';
fout<<setprecision(12)<<fixed;
for (i=1;i<=top;++i)
fout<<a[st[i]].x<<" "<<a[st[i]].y<<'\n';
return 0;
}