Pagini recente » Cod sursa (job #1619756) | Cod sursa (job #2629573) | Cod sursa (job #3244058) | Cod sursa (job #913570) | Cod sursa (job #1399359)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;
const int NMAX=120004;
int n, i;
typedef pair<double, double> punct;
punct v[NMAX], st[NMAX];
inline double panta(const punct &a,const punct &b,const punct &c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
inline int cmp(const punct& a, const punct& b)
{
return panta(v[1], a, b)<0;
}
void sortare()
{
int i, p=1;
for (i=2; i<=n; ++i)
if (v[i]<v[p])
p=i;
swap(v[1],v[p]);
sort(v+2,v+n+1,cmp);
}
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n;
for(i=1; i<=n; i++)
cin>>v[i].x>>v[i].y;
sortare();
st[1]=v[1];
st[2]=v[2];
int vf=2;
for(i=3; i<=n; i++)
{
while(vf>=2&&panta(st[vf-1],st[vf],v[i])>0)
vf--;
st[++vf]=v[i];
}
cout<<vf<<'\n';
for(i=vf; i>=1; i--)
cout<<setprecision(8)<<fixed<<st[i].x<<' '<<st[i].y<<'\n';
return 0;
}