#include <bits/stdc++.h>
using namespace std;
#define eps 1e-12
const double INF = 1e18;
const int nmax=100005;
ifstream f("text.in");
ofstream g("text.out");
struct punct //structura de date pentru a reprezenta un punct in plan
{
double X, Y;
};
punct v[nmax];
int s[nmax],ok[nmax];
struct cerc //structura de date pentru a reprezenta un cerc in plan
{
punct C;
double R;
};
double distanta(punct& a, punct& b)//functie ce returneaza distanta dintre doua puncte in plan
{
return sqrt(pow(a.X - b.X, 2)+ pow(a.Y - b.Y, 2));
}
bool valid(cerc& c, punct& p)//functie ce returneaza true sau false daca punctul este in interiorul cercului, respectiv pe marginea acestuia
{
return distanta(c.C, p) <= c.R;
}
punct centrucerc(double bx, double by, double cx, double cy)//functie ce returneaza centrul cercului definit de 3 puncte
{
double B = bx * bx + by * by;
double C = cx * cx + cy * cy;
double D = bx * cy - by * cx;
return { (cy * B - by * C) / (2 * D),(bx * C - cx * B) / (2 * D) };
}
cerc cerc3( punct& A, punct& B, punct& C)//functie ce returneaza un cerc unic ce intersecteaza 3 puncte
{
punct I = centrucerc(B.X - A.X, B.Y - A.Y,C.X - A.X, C.Y - A.Y);
I.X += A.X;
I.Y += A.Y;
return { I, distanta(I, A) };
}
cerc cerc2( punct& A, punct& B)//functie ce returneaa cel mai mic cerc ce intersecteaza 2 puncte
{
punct C = { (A.X + B.X) / 2.0, (A.Y + B.Y) / 2.0 };// centrul este mijlocul segementului AB
return { C, distanta(A, B) / 2.0 };// raza este 1/2 din lungimea segmentului AB
}
bool cercvalid(cerc& c,vector<punct>& P)//functie ce verifica daca cercul contine punctele date
{
for(punct& p : P)
if (!valid(c, p))
return false;
return true;
}
cerc cercminim(vector<punct>& P)//functie ce returneaza cercul minim pentru n<=3
{
assert(P.size() <= 3);
//{
if (P.empty())
{
return { { 0, 0 }, 0 };
}
else if (P.size() == 1)
{
return { P[0], 0 };
}
else if (P.size() == 2)
{
return cerc2(P[0], P[1]);
}
for (int i = 0; i < 3; i++) //verficam daca cercul minim poate fi determinat de 2 puncte
{
for (int j = i + 1; j < 3; j++)
{
cerc c = cerc2(P[i], P[j]);
if (cercvalid(c, P))
return c;
}
}
return cerc3(P[0], P[1], P[2]);
//}
}
// n e numarul de puncte care nu au fost parcurse pana acum
cerc solve(vector<punct>& P,vector<punct> R, int n)//setul R contine puncte de pe circumferinta cercului
{
if (n == 0 || R.size() == 3) //cazul de baza cand toate punctele au fost procesate sau R contine 3 puncte
{
return cercminim(R);
}
int idx = rand() % n;//alegem un punct la intamplare
punct p = P[idx];
swap(P[idx], P[n - 1]);
cerc d = solve(P, R, n - 1);//obtinem cercul minim din setul P excluzand punctul p
if (valid(d, p))
{
//daca d il contine pe p, returnam d
return d;
}
R.push_back(p);//altfel, p se afla pe circumferinta cercului
return solve(P, R, n - 1);// returnam cercul minim pentru P-{p} si R U {p}
}
int cmp1(double a,double b)
{
if (a+eps<b) return 1;
if (b+eps<a) return -1;
return 0;
}
bool cmp(punct &a, punct &b)//functia de comparare a cooordonatelor
{
int t;
t=cmp1(a.X,b.X);
if (t!=0) return t==1;
return (cmp1(a.Y,b.Y)==1);
}
int semn(punct a,punct b,punct c) //se verifica daca C nu apartine dreptei AB
{
double A,B,C;
A = a.Y-b.Y;
B = b.X-a.X;
C = a.X*b.Y - b.X*a.Y;
return cmp1(A*c.X+B*c.Y+C,0);
}
int n,h,i;
void solve2()
{
int k,q;
sort(v+1,v+n+1,cmp);
s[1]=1;
s[2]=2; //in stiva s se introduce cel mai din stanga punct si cel de-al doilea care urmeaza sa fie verificat
ok[2]=1;
k=2;
i=3;
q=1;
while (!ok[1])
{
while(ok[i])
{
if(i==n)q=-1;
i+=q;
}
while(k>=2 && semn(v[s[k-1]],v[s[k]],v[i])==-1)
{
ok[s[k--]]=0;
}
s[++k]=i;
ok[i]=1;
}
h=k-1;
}
int c;
punct w;
vector <punct> P;
int main()
{
//f>>c;
c=2;
f>>n;
if(c==1)
{
for(int i=1; i<=n; i++)
{
f>>w.X>>w.Y;
P.push_back(w);
}
vector<punct> P_copy = P;
cerc cm=solve(P_copy, {}, P_copy.size());
g<<cm.C.X <<" "<< cm.C.Y<< " "<<cm.R << endl;
}
else
{
for(int i=1;i<=n;i++)
{
f>>v[i].X>>v[i].Y;
}
solve2();
g<<h;
g<<fixed<<setprecision(12);
for(int i=2; i<=h+1; i++)
{
g<<v[s[i]].X<<" "<<v[s[i]].Y<<'\n';
}
}
return 0;
}