Cod sursa(job #693022)
#include<fstream>
#include<iomanip>
using namespace std;
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"
#define inf 1000000
#define MaxN 50000
fstream f(IN, ios::in), g(OUT, ios::out);
double x, y, Px, Py, V, maxim;
int last, n, i, p, R[MaxN], q;
bool ok;
struct{
double x, y, visited;
}point[MaxN];
double compute(double x1, double y1, double x2, double y2, double x3, double y3)
{
double R=0;
R=x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3;
return R;
}
int main()
{
f>>n;
Px=inf; Py=inf;
for(i=1; i<=n; i++)
{
f>>x>>y;
point[i].x=x; point[i].y=y; point[i].visited=0;
if(x<Px){ Px=x; Py=y; p=i; }
else if(x==Px && y<Py){ Px=x; Py=y; p=i; }
}
point[p].visited=1;
last=p;
q=1;
R[q]=last;
ok=true;
while(ok==true)
{
ok=false;
maxim=-inf;
for(i=1; i<=n; i++)
{
if(point[i].visited==0 && point[i].x>=point[last].x)
{
ok=true;
V=compute(point[last].x, point[last].y, point[last].x-1, point[last].y, point[i].x, point[i].y);
if(V>maxim){ maxim=V; p=i; }
}
}
if(ok==true)
{
last=p;
q++;
R[q]=last;
if(maxim==0)g<<"(ANT SCOS DIN CONVEX_HULL) ";
point[p].visited=1;
}
}
ok=true;
while(ok==true)
{
ok=false;
maxim=inf;
for(i=1; i<=n; i++)
{
if(point[i].visited==0 && point[i].x<=point[last].x)
{
ok=true;
V=compute(point[last].x, point[last].y, point[last].x-1, point[last].y, point[i].x, point[i].y);
if(V<maxim){ maxim=V; p=i; }
}
}
if(ok==true)
{
last=p;
q++;
R[q]=last;
point[p].visited=1;
}
}
g<<q<<endl;
for(i=1; i<=q; i++)
g<<fixed<<setprecision(12)<<point[R[i]].x<<" "<<point[R[i]].y<<"\n";
}