Pagini recente » Cod sursa (job #1092854) | Cod sursa (job #110751) | Cod sursa (job #184955) | Cod sursa (job #370179) | Cod sursa (job #2839117)
#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[100005];
long long i,n,nr,st[100005],sel[100005],ung[1000005],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;
}
}
nr--;
out<<nr;
for (i=nr-1;i>=1;--i)
out<<a[st[i]].xx<<" "<<a[st[i]].yy<<'\n';
return 0;
}