Cod sursa(job #627170)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 29 octombrie 2011 11:05:01
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.06 kb
#include <stdio.h>
#include <math.h>
#define INF 1000000010

struct nod{
   double x,y;  
}v[120005];
double panta[120005];
int convex[120005];//tine indicii punctelor care apar ca varfuri ale infasuratorii convexe
bool viz[120005];

int ppoz(int li,int ls){
    int ii=1,jj=0;
    double c;
    nod aux;
  while(li<ls){
    if(panta[li]>panta[ls]){
       c=panta[li];
       panta[li]=panta[ls];
       panta[ls]=c;
       
       aux=v[li];
       v[li]=v[ls];
       v[ls]=aux;

       
       c=ii;
       ii=-jj;
       jj=-c;
       
    }
   li+=ii;
   ls+=jj;
	
  }  
   

  return li;
}


void quick(int li,int ls){
   int k;
   if(li<ls){
       k=ppoz(li,ls);
       quick(li,k-1);
       quick(k+1,ls);
   }
}

bool e_convex(int vf){
   //verific daca punctele care au indicii convex[vf-2], convex[vf-1] si convex[vf]
   //fac un inghi mai mic de 180grade...
   //verific asta facand determinantul triunghiului...
   double xa=v[convex[vf-2]].x,ya=v[convex[vf-2]].y,xb=v[convex[vf-1]].x,yb=v[convex[vf-1]].y,xc=v[convex[vf]].x,yc=v[convex[vf]].y;
   double aux1=(xa-xc)*(yb-yc),aux2=(xb-xc)*(ya-yc);//daca aux1-aux2 e pozitiv e bine
   if(aux1>=aux2)return 1;
   return 0;
}


int main(){
  int n,i;
  int ind;//indicele punctului celui mai din stanga, cel mai de jos
  double xind=INF,yind=INF;
  FILE *fin=fopen("infasuratoare.in","r");
  FILE *fout=fopen("infasuratoare.out","w");
  fscanf(fin,"%d",&n);
  
  for(i=0;i<n;i++){
     fscanf(fin,"%lf %lf",&v[i].x,&v[i].y);//long float, adica double
     //printf("(%lf,%lf) \n",v[i].x,v[i].y);
     if(v[i].x<xind){
          ind=i;
          xind=v[i].x;
          yind=v[i].y;
     }else if((v[i].x==xind)&&(v[i].y<yind)){ind=i;yind=v[i].y;}
}
  fclose(fin);
  //punctul ind este sigur pe infasuratoare, e un varf
  //calculez panta tutor punctelor fata de acest punct ales
  for(i=0;i<n;i++){
     if(v[i].x!=xind){
       panta[i]=(v[i].y-yind)/(v[i].x-xind);
     }else{
        //pt punctul ales panta va fi zero
        if(v[i].y==yind){panta[i]=0;}
          else if(v[i].y<yind)panta[i]=-INF;//asigur faptul ca punctul de pe aceeasi verticala cu punctul ales, dar dedesubt e primul ales
                 else panta[i]=INF;
     }
  }  
  
  //calculez si sortez descresc dupa panta
  quick(0,n-1);
  //dupa sortare nu mai stiu pe ce loc se afla (xind, yind)
  for(i=0;i<n;i++)
    if(v[i].x==xind && v[i].y==yind){ind=i;break;}

 //printf("am ales punctul (%lf,%lf) de start\n",v[ind].x,v[ind].y);
 //for(i=0;i<n;i++)printf("(%lf,%lf) ",v[i].x,v[i].y);
// printf("\n");
  int vf=0;//indicele varfului stivei convex[]
  //adaug primele doua puncte de mana...
  convex[vf++]=ind;//primul este punctul ales
  convex[vf++]=0;//al doilea este punctul cu panta cea mai mica fata de punctul dat
  //vreau sa mai adaug un punct
  i=1;//aici am ajuns in vector
  do{
   //verific punctul i
   convex[vf]=i; 
   while(!e_convex(vf)){
      vf--;
      convex[vf]=i; 
   }
   vf++;
   i++; 
  }while(i<n);
  
   //afisez convex
   fprintf(fout,"%d\n",vf);
   for(i=0;i<vf;i++)
      fprintf(fout,"%lf %lf\n",v[convex[i]].x,v[convex[i]].y);
   

  fclose(fout);
  return 0;
}