Cod sursa(job #264681)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 22 februarie 2009 16:26:21
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<fstream>
using namespace std;

float t[120010];
struct punct {float x,y;} v[120010],p,aux;

int i,j,n,k,poz,s[120010];

int pozitie(int i, int j)

 { int di=1,dj=0,aux2;
   float aux3;
   while(i<j)

   { if(t[i]>t[j]||t[i]==t[j]&&v[i].x>v[j].x)

         { aux3=t[i]; t[i]=t[j]; t[j]=aux3;

           aux2=di; di=dj; dj=aux2;

           aux=v[i]; v[i]=v[j]; v[j]=aux;
         }
      i+=di;
      j-=dj;
   }

  return i;
  }
void quick(int s, int d)

 { if(s<d)

   { int p=pozitie(s,d);

      quick(s,p-1);
      quick(p+1,d);
   }
 }

void elimin(int &k)

 {  long double S;

    int a=s[k-1],b=s[k];

    S= v[a].x*v[b].y-
       v[i].x*v[b].y+
       v[b].x*v[i].y-
       v[b].x*v[a].y+
       v[i].x*v[a].y-
       v[a].x*v[i].y;

    if(S<0) elimin(--k);
  }

int main()

{

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

f>>n;   p.x=1000000000; p.y=1000000000;

for(i=0;i<n;i++)

 {
   f>>v[i].x>>v[i].y;

     if(v[i].x<p.x||v[i].x==p.x&&v[i].y<p.y) {poz=i; p=v[i];}
 }

aux=v[0]; v[0]=v[poz]; v[poz]=aux;

 for(i=1;i<n;i++)

  t[i]=(float)(v[i].y-p.y)/(v[i].x-p.x);

quick(1,n-1);

s[1]=0; s[2]=1; k=2;

 for(i=2;i<n;i++)

  { if(t[i]!=t[i+1])

     {  elimin(k);

        s[++k]=i;
      }
  }


g<<k<<'\n';

for(i=1;i<=k;i++)

 g<<v[s[i]].x<<" "<<v[s[i]].y<<'\n';


f.close();
g.close();
return 0;
}