Pagini recente » Cod sursa (job #2643208) | Cod sursa (job #138254) | Cod sursa (job #4133) | Cod sursa (job #12577) | Cod sursa (job #2839050)
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct nya{long double xx,yy;};
nya a[500005];
long long i,n,nr,st[500005],sel[500005],ung[5000005],j;
long double mi,un1,un2,ii,jj,jj1,jj2;
int cmp(nya a,nya b)
{
return make_pair(a.xx,a.yy)<make_pair(b.xx,b.yy);
}
long double det(nya a,nya b,nya c)
{
return a.xx*b.yy+b.xx*c.yy+a.yy*c.xx-b.yy*c.xx-a.yy*b.xx-a.xx*c.yy;
}
int main()
{
cin>>n;
for (i=1;i<=n;++i)
{
cin>>a[i].xx>>a[i].yy;
}
sort(a+1,a+n+1,cmp);
st[1]=1;
st[2]=2;
nr=2;
for (i=3;i<=n;++i)
{
while (nr>1&&det(a[st[nr-1]],a[st[nr]],a[i])>=0)
{
sel[st[nr]]=0;
nr--;
}
sel[i]=1;
st[++nr]=i;
}
for (i=n;i>=1;--i)
{
if (sel[i]==0)
{
while (nr>1&&det(a[st[nr-1]],a[st[nr]],a[i])>=0)
{
sel[st[nr]]=0;
nr--;
}
sel[i]=1;
st[++nr]=i;
}
}
nr--;
cout<<nr<<'\n';
for (i=nr;i>=1;--i)
cout<<a[st[i]].xx<<" "<<a[st[i]].yy<<'\n';
return 0;
}