Cod sursa(job #309187)

Utilizator mihaionlyMihai Jiplea mihaionly Data 29 aprilie 2009 20:35:35
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <iomanip>
#include <math.h>
#define dim 120010
using namespace std;
ifstream f("infas.in");
ofstream g("infas.out");
int n,k;
typedef struct
 {
 double x,y,u1,u2;
 } Punct;
Punct p[dim],pv,s[dim];
void swap(Punct &p1,Punct &p2)
 {
 Punct px=p1;
 p1=p2;
 p2=px;
 }
void read()//citeste punctele si stabileste pivotul
 {
 int i,j;
 f>>n;
 for(i=1;i<=n;i++)
  {
  f>>p[i].x>>p[i].y;
  if(i==1)
   {
   pv=p[i];
   j=i;
   }
  else if(p[i].y-pv.y<0)
   {
   pv=p[i];
   j=i;
   }
  else if(p[i].y-pv.y==0&&p[i].x-pv.x<0)
   {
   pv=p[i];
   j=i;
   }
  }
 swap(p[j],p[1]);//plaseaza pivotul pe prima pozitie
 }
void assign()
 {
 int i;
 for(i=2;i<=n;i++)
  {
  p[i].u1=(p[i].y-p[1].y);
  p[i].u2=(p[i].x-p[1].x);
  }
 }
void quicks(int l,int r)
 {
 int i,j;
 j=l-1;
 for(i=l;i<=r;i++)
  {
  if((p[i].u1*p[r].u2)<=(p[r].u1*p[i].u2))
   swap(p[i],p[++j]);
  }
 if(l<j-1)
  quicks(l,j-1);
 if(r>j+1)
  quicks(j+1,r);
 }
double clock(Punct p1,Punct p2,Punct p3)
 {
 return (p3.x-p1.x)*(p2.y-p1.y)-(p3.y-p1.y)*(p2.x-p1.x);
 }
void graham()
 {
 assign();
 quicks(2,n);
 p[n+1]=s[++k]=p[1];
 int i;
 for(i=2;i<=n;i++)
  {
  if(clock(s[k],p[i],p[i+1])<0)
   s[++k]=p[i];
  }
 }
void write()
 {
 g<<k<<endl;
 for(int i=1;i<=k;i++)
  {
  g<<setprecision(6)<<s[i].x;
  g<<" ";
  g<<setprecision(6)<<s[i].y<<endl;
  }
/* g<<setprecision(6)<<s[i].x;
 g<<" ";
 g<<setprecision(6)<<s[i].y<<endl;
  */
 }
int main()
 {
 read();
 graham();
 write();
 return 0;
 }