Cod sursa(job #264728)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 22 februarie 2009 17:40:07
Problema Infasuratoare convexa Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include<stdio.h>
using namespace std;

float t[120010];
struct punct {long double 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||t[i]==t[j]&&v[i].x==v[j].x&&v[i].y<v[j].y)

         { 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()

{

FILE *f=fopen("infasuratoare.in","r");

fscanf(f,"%d",&n);

p.x=1000000000; p.y=1000000000;

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

 {
   fscanf(f,"%Lf %Lf",&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];}
 }

fclose(f);

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);

        if(v[s[k]].y==v[s[k-1]].y&&v[s[k]].y==v[i].y||v[s[k]].x==v[s[k-1]].x&&v[s[k]].x==v[i].x) s[k]=i;

          else s[++k]=i;
      }
  }

FILE *g=fopen("infasuratoare.out","w");

fprintf(g,"%d\n",k);

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

 fprintf(g,"%0.6Lf %0.6Lf\n",v[s[i]].x,v[s[i]].y);


fclose(g);
return 0;
}