Cod sursa(job #531308)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 9 februarie 2011 13:38:04
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<fstream>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct punct
{
   double x,y;
} p[120001],IN[120001];

int n,nr;

void read();
void solve();
void write();
int cmp(punct A,punct B);
double uhi(punct A,punct B,punct C);
double dist(punct A,punct B);

int main()
{
   read();
   solve();
   write();
   f.close();
   g.close();
   return 0;
}

void read()
{
	int i;
   f>>n;
   for (i=1;i<=n;++i)
      f>>p[i].x>>p[i].y;
}

void solve()
{
   int i,pos;
   double unghi;
   pos=1;
   for (i=2;i<=n;++i)
      if ((p[i].y<p[pos].y)||(p[i].y==p[pos].y&&p[i].x<p[pos].x))
         pos=i;
   swap(p[1],p[pos]);
   IN[1]=p[1];
   sort(p+2,p+1+n,cmp);
   IN[2]=p[2];
   nr=2;
   
   for (i=3;i<=n;++i)
   {
      unghi=uhi(IN[nr],p[i],IN[nr-1]);
      while (unghi<0||(!unghi&&dist(IN[1],IN[i])>dist(IN[1],IN[nr])))
      {
         --nr;
         unghi=uhi(IN[nr],p[i],IN[nr-1]);
      }
      IN[++nr]=p[i];
   }
}

void write()
{
   int i;
   g<<nr<<'\n';
   for (i=1;i<=nr;++i)
      g<<IN[i].x<<' '<<IN[i].y<<'\n';
}

int cmp(punct A,punct B)
{
	return (uhi(p[1],A,B)>0);
}


double uhi(punct A,punct B,punct C)
{
	return (A.x*B.y+B.x*C.y+A.y*C.x-C.x*B.y-C.y*A.x-B.x*A.y);
}

double dist(punct A,punct B)
{
	double t1,t2;
	t1=A.x-B.x;
	t2=A.y-B.y;
	t1*=t1;
	t2*=t2;
	return sqrt(t1+t2);
}