Pagini recente » Cod sursa (job #489908) | Cod sursa (job #599489) | Cod sursa (job #2032596) | Cod sursa (job #2639697) | Cod sursa (job #1395543)
//#include <iostream>
#include <fstream>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
#include <algorithm>
#define x first
#define y second
#define mp make_pair
#define db double
#define LE 120666
#include <iomanip>
#define cout g
pair<db,db> B[LE];
pair<db,db> Pmin;
db cross(pair<db,db> i1,pair<db,db> i2,pair<db,db> i3)
{
i2.x-=i1.x,i3.x-=i1.x;
i2.y-=i1.y,i3.y-=i1.y;
return (i2.y*i3.x-i2.x*i3.y);
}
bool comp (pair<db,db> i1,pair<db,db> i2)
{
db val=cross(Pmin,i1,i2);
if (val==0) return i1.y>i2.y;
return (val>0.0);
}
int solve(pair<db,db> A[],int N)
{
Pmin=A[1];
int i,ind_min=1;
for(i=1; i<=N; ++i)
if (A[i].y<Pmin.y)
Pmin=A[i],ind_min=i;
swap(A[ind_min],A[1]);
sort(A+2,A+1+N,comp);
int k=2;
B[1]=A[1];
B[2]=A[2];
for(i=3; i<=N; ++i)
{
while (k>=2&&cross(B[k-1],B[k],A[i])<0.0) --k;
B[++k]=A[i];
}
return k;
}
pair<db,db> V[LE];
int main()
{
int n,i;
f>>n;
for(i=1; i<=n; ++i) f>>V[i].x>>V[i].y;
int k=solve(V,n);
cout<<k<<'\n';
cout<<fixed;
cout<<setprecision(10);
for(i=k; i>=1; --i)
{
cout<<B[i].x<<" "<<B[i].y<<'\n';
}
return 0;
}