Pagini recente » Cod sursa (job #2674275) | Cod sursa (job #1814802) | Cod sursa (job #961811) | Cod sursa (job #2518414) | Cod sursa (job #1096724)
#include <fstream>
#include <algorithm>
#include <stack>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef pair<double,double> punct;
punct a[120001];
punct st[120001];
double rotation(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);
}
bool cmp(const punct& A,const punct& B)
{
return rotation(a[1],A,B)<0;
}
int main()
{
int n;
fin>>n;
int pos = 1;
for(int i=1;i<=n;i++)
{
fin>>a[i].x>>a[i].y;
if(a[i] < a[pos])
pos = i;
}
swap(a[1],a[pos]);
sort(a+2,a+1+n,cmp);
st[1] = a[1];
st[2] = a[2];
int k = 2;
for(int i=3;i<=n;i++)
{
while(k>=2 && rotation(st[k-1],st[k],a[i])>0)
--k;
st[++k] = a[i];
}
fout<<k<<'\n';
for(int i=k;i>0;i--)
fout<<setprecision(9)<<fixed<<st[i].x<<' ' <<st[i].y<<'\n';
fin.close();
fout.close();
return 0;
}