Pagini recente » Cod sursa (job #1776277) | Cod sursa (job #1393896) | Cod sursa (job #1885154) | Cod sursa (job #22166) | Cod sursa (job #1372689)
//#include <iostream>
#include <fstream>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
#include <iomanip>
#define x first
#define y second
#define mp make_pair
#define db double
#define LE 120666
#define inf (1<<30)
#include <algorithm>
#define cout g
#define eps 0.0000000000001
pair<db,db> A[LE];
int ind[LE],st[LE];
db mul(pair<db,db> ix,pair<db,db> i1,pair<db,db> i2)
{
i1=mp(i1.x-ix.x,i1.y-ix.y);
i2=mp(i2.x-ix.x,i2.y-ix.y);
return i1.y*i2.x-i1.x*i2.y;
}
bool comp(int i1,int i2)
{
db val=mul(A[1],A[i1],A[i2]);
if (val>-eps&&val<eps) return A[i1].y>A[i2].y;
return val>0;
}
int main()
{
int n,i,imin;
f>>n;
pair<db,db> minv=mp(inf,inf);
for(i=1; i<=n; ++i)
{
f>>A[i].x>>A[i].y;
if (mp(A[i].y,A[i].x)<minv) minv=mp(A[i].y,A[i].x),imin=i;
ind[i]=i;
}
// swap(A[imin],A[1]);
swap(ind[imin],ind[1]);
sort(ind+2,ind+n+1,comp);
st[1]=ind[1];
st[2]=ind[2];
int k=2;
for(i=3; i<=n; ++i)
{
while (k>=2&&mul(A[st[k-1]],A[st[k]],A[ind[i]])<-eps) --k;
st[++k]=ind[i];
}
//swap(A[imin],A[1]);
cout<<fixed;
cout<<setprecision(10);
cout<<k<<'\n';
for(i=k; i>=1; --i)
cout<<A[st[i]].x<<" "<<A[st[i]].y<<'\n';
return 0;
}