Cod sursa(job #676479)

Utilizator biroBiro Alexandru biro Data 9 februarie 2012 10:14:59
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.12 kb
#include <algorithm>
#define INF 1000000

using namespace std ;

struct punct{
  float x ;
  float y ;
  float p ;
} ; 

float panta (punct A,punct B) { 
  /*
  (Ay-By)/(Ax-Bx)
  */
  if (A.x==B.x) {
    return INF ;  
  }
  else 
  return (A.y-B.y)/(A.x-B.x) ;
}
int comp(punct A,punct B) {
  if (A.p>B.p) return 0 ;
  else return 1 ;
}

punct a[120001] ;
punct stiva[120001] ;
int cap ;
int right_turn(punct A,punct B,punct C){
  float puc=(B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x) ;
  if (puc<=0)return 1 ;
  else return 0;
}

int main() {
  freopen ("infasuratoare.in","r",stdin) ;
  freopen ("infasuratoare.out","w",stdout) ;
  
  int n ; 
  scanf ("%d" , &n) ;
  float xx , yy , tmp ;
  scanf ("%f%f" , &a[1].x , &a[1].y) ;
  float mx=a[1].x , my=a[1].y ;
  for (int i=2 ; i<=n ; ++i) {
    scanf ("%f%f" , &xx , &yy) ;
    if (xx<mx) {
      mx=xx ;
      my=yy ;  
      tmp=a[1].x ;
      a[1].x=xx ;
      a[i].x=tmp ;
      tmp=a[1].y ;
      a[1].y=yy ;
      a[i].y=tmp ;
    }
    else {
      if (xx==mx)   {
        if (yy<my)  {
          mx=xx ;
          my=yy ;  
          tmp=a[1].x ;
          a[1].x=xx ;
          a[i].x=tmp ;
          tmp=a[1].y ;
          a[1].y=yy ;
          a[i].y=tmp ;
        }// else yy <
        else {
          a[i].x=xx ;
          a[i].y=yy ;    
        }
      }//if ==
      else {
        a[i].x=xx ;
        a[i].y=yy ;        
      }
    }//else
  }//for
  a[1].p=-INF ;
  for (int i=2 ; i<=n ; ++i) {
    a[i].p=panta(a[i],a[1]) ;
  }      
                                                                                                        
  sort (a+2,a+n+1,comp) ;

  stiva[++cap]=a[1] ;
  stiva[++cap]=a[2] ;
 
  for (int i=3 ; i<=n ; ++i)  {
    if (right_turn(a[i],stiva[cap],stiva[cap-1])==1) {
      stiva[++cap]=a[i] ;  
    }
    else {
      while (right_turn(a[i],stiva[cap],stiva[cap-1])==0) {
        cap-=1 ; 
      }  
      stiva[++cap]=a[i] ;
    }
  }

  printf ("%d\n" , cap) ;
  for (int i=1 ; i<=cap ;++i) printf ("%f %f\n" , stiva[i].x , stiva[i].y) ;
  
  return 0;  
}