Pagini recente » Cod sursa (job #1507455) | Cod sursa (job #1791991) | Cod sursa (job #165407) | Cod sursa (job #2278606) | Cod sursa (job #2839122)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct nya{long double xx,yy;};
nya a[400005];
long long i,n,nr,st[400005],sel[400005],ung[4000005],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);
}
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()
{
in>>n;
for (i=1;i<=n;++i)
{
in>>a[i].xx>>a[i].yy;
}
sort(a+1,a+n+1,cmp);
st[1]=1;
st[2]=2;
nr=2;
sel[2]=1;
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;
}
}
out<<nr-1<<'\n';
for (i=nr-1;i>=1;--i)
out<<a[st[i]].xx<<" "<<a[st[i]].yy<<'\n';
return 0;
}