Pagini recente » Cod sursa (job #251114) | Solutii preONI 2007, Runda 3 | Cod sursa (job #1159548) | Cod sursa (job #2576040) | Cod sursa (job #2015731)
#include <fstream>
#define nmax 120005
#include <iomanip>
using namespace std;
fstream f1("infasuratoare.in", ios::in);
fstream f2("infasuratoare.out", ios::out);
struct punct
{
double x, y;
}p[nmax], aux, stiva[nmax];
long int n, vf;
void citire()
{
long int i, poz;
f1>>n;
for(i=1; i<=n; i++)
f1>>p[i].x>>p[i].y;
poz=1;
for(i=2; i<=n; i++)
if((p[i].x< p[poz].x)||((p[i].x== p[poz].x)&&(p[i].y< p[poz].y))) poz=i;
aux= p[1];
p[1]=p[poz];
p[poz]=aux;///p[1]= punct cu xmin
}
double crossp(punct p0, punct p1, punct p2)
{
return ((p1.x- p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x));
}
void sortare()
{
///sortezi punctele trig comparandu-le 2 cate 2 in fct de produsul vectorial
long int i, j, gap;
for(gap=n/2; gap>=1; gap/=2)
for(i=gap+1; i<=n; i++)
{
aux=p[i];
for(j=i-gap; (j>=1)&&(crossp(p[1], p[j], aux)<0); j-=gap)
p[j+gap]=p[j];
p[j+gap]=aux;
}
}
void graham()
{
long int i;
stiva[1]=p[1];
stiva[2]=p[2];
vf=2;
for(i=3; i<=n; i++)
{
if(crossp(stiva[vf-1], stiva[vf], p[i])>0) {vf++; stiva[vf]=p[i];}
else {stiva[vf]=p[i];}
}
}
void afisare()
{
long int i;
f2<<vf<<"\n";
for(i=1; i<=vf; i++)
f2<<fixed<<setprecision(9)<<stiva[i].x<<' '<<stiva[i].y<<"\n";
}
int main()
{
citire();
sortare();
graham();
afisare();
return 0;
}