Cod sursa(job #1559408)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 30 decembrie 2015 18:28:59
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <cstdio>
#define maxn 120002
#define EPS 1e-12
#include <algorithm>
#include <iomanip>

using namespace std;

struct pereche{
  double x,y;
} V[maxn];
int N,h = 2,S[maxn];
bool viz[maxn];

inline void swap(pereche &a,pereche &b){
  pereche aux = a;
  a = b;
  b = aux;
}

inline double produs_in_cruce(const pereche &A,const pereche &B,const pereche &C){
   return (A.x - C.x) * (B.y - C.y) - (B.x - C.x) * (A.y - C.y);
}

void quick_sort(pereche a[],int inf,int sup){

  int i = inf,j = sup;
  pereche x = a[(i+j)/2];
  do{

    while(i < sup && (a[i].x <= x.x))i++;
    while(j > inf && (a[j].x >= x.x))j--;

    if(i<=j){
      swap(a[i],a[j]);
      i++;j--;
    }
  }while( i <= j );

  if(inf < j)quick_sort(a,inf,j);
  if(i < sup)quick_sort(a,i,sup);

}

int main(){

  freopen("infasuratoare.in","r",stdin);
  freopen("infasuratoare.out","w",stdout);

  scanf("%d ",&N);
  int i,p = 1;
  for(i = 1;i <= N;++i)
    scanf("%lf %lf ",&V[i].x,&V[i].y);
  
  //quick_sort(V,1,N);
  sort(V+1,V+N+1);
  S[1] = 1;
  S[2] = 2;
  viz[2] = true;
  
  for(i = 1;i > 0; i += (p = (i == N ? -p : p)))if(viz[i] == false){
    
    while(h >= 2 && produs_in_cruce(V[S[h-1]],V[S[h]],V[i]) < EPS)
       viz[S[h--]] = false;
    S[++h] = i;
    viz[i] = true;
    
  }
  
  printf("%d\n",h-1);
  for(i = 1;i < h;++i)printf("%lf %lf\n",V[S[i]].x,V[S[i]].y);
  printf("\n");
  return 0;
}