Pagini recente » Cod sursa (job #1001116) | Cod sursa (job #539616) | Cod sursa (job #2421216) | Cod sursa (job #1562005) | Cod sursa (job #2288625)
#include<fstream>
#include<algorithm>
#include<iomanip>
#define x first
#define y second
#define pp pair < double, double >
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pp p[120010];
int i,n,st[120010];
double determ(pp a, pp b, pp c)
{
double ans= a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - c.y*a.x - a.y*b.x;
return ans;
}
int main()
{
fin>>n;
for(i=1;i<=n;i++)
{
fin>>p[i].x>>p[i].y;
}
sort(p+1,p+n+1);
st[1]=1;
st[2]=2;
st[0]=2;
for(i=3;i<=n;i++)
{
while(st[0]>1 && determ(p[st[st[0]-1]],p[st[st[0]]],p[i])>0)
st[0]--;
st[++st[0]]=i;
}
for(i=n-1;i>=1;i--)
{
while(determ(p[st[st[0]-1]],p[st[st[0]]],p[i])>0)
st[0]--;
st[++st[0]]=i;
}
fout<<st[0]-1<<'\n';
for(i=st[0]-1;i>=1;i--)
fout<<setprecision(6)<<fixed<<p[st[i]].x<<' '<<p[st[i]].y<<'\n';
fin.close();
fout.close();
return 0;
}