Pagini recente » Cod sursa (job #2494716) | Cod sursa (job #2604711) | Cod sursa (job #1144519) | Cod sursa (job #497695) | Cod sursa (job #2170000)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define nmax 120005
#define inf 1000000005
using namespace std;
fstream f1("infasuratoare.in", ios::in);
fstream f2("infasuratoare.out", ios::out);
int n, vf;
struct punct
{
double x, y;
}p[nmax], stiva[nmax];
double det(punct a, punct b, punct c)
{
return (a.x*b.y+ b.x*c.y+ c.x*a.y- c.x*b.y - a.x*c.y- a.y*b.x);
}
bool cmp(punct a, punct b)
{
return (det(p[1], a, b)>0);
}
void citire()
{
int i, ind;
double xmin=inf, ymin=inf;
f1>>n;
for(i=1; i<=n; i++)
f1>>p[i].x>>p[i].y;
for(i=1; i<=n; i++)
if((p[i].x< xmin)||((p[i].x==xmin)&&(p[i].y< ymin)))
{
xmin=p[i].x;
ymin=p[i].y;
ind=i;
}
swap(p[1], p[ind]);
sort(p+2, p+n+1, cmp);
}
void graham()
{
int i;
vf=1; stiva[vf]=p[1];
vf++; stiva[vf]=p[2];
for(i=3; i<=n; i++)
{
while((vf>=2)&&(det(p[i], stiva[vf], stiva[vf-1])>0)) vf--;
vf++; stiva[vf]=p[i];
}
f2<<vf<<"\n";
for(i=1; i<=vf; i++)
f2<<fixed<<setprecision(12)<<stiva[i].x<<' '<<stiva[i].y<<"\n";
}
int main()
{
citire();
graham();
return 0;
}