Cod sursa(job #1547331)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 9 decembrie 2015 12:21:18
Problema Infasuratoare convexa Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.8 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_N 120000
#define EPS 1e-10

typedef struct {
  double x, y;
} Point;

typedef struct {
  int s[MAX_N];
  int ss;
} stack;

Point v[MAX_N];
stack L, U;

void myqsort( int begin, int end ) {
  int b = begin, e = end;
  Point pivot = v[rand() % (end - begin + 1) + begin], tmp;

  while ( b <= e ) {
    while ( v[b].x < pivot.x || (v[b].x == pivot.x && v[b].y < pivot.y) ) b++;
    while ( v[e].x > pivot.x || (v[e].x == pivot.x && v[e].y > pivot.y) ) e--;
    if ( b <= e ) {
      tmp = v[b]; v[b] = v[e]; v[e] = tmp;
      b++; e--;
    }
  }
  if ( begin < e ) myqsort( begin, e );
  if ( b < end ) myqsort( b, end );
}

// A.x A.y 1
// B.x B.y 1
// C.x C.y 1
__inline__ double ccw( Point *A, Point *B, Point *C ) {
  return ( C->x - A->x ) * ( B->y - A->y ) - ( C->y - A->y ) * ( B->x - A->x );
}

int main(void) {
  FILE *fin, *fout;
  int N, i;

  fin = fopen( "infasuratoare.in", "r" );
  fscanf( fin, "%d", &N );
  for ( i = 0; i < N; i++ ) {
    fscanf( fin, "%lf%lf", &v[i].x, &v[i].y );
  }
  fclose( fin );

  myqsort( 0, N - 1 );

  for ( i = 0; i < N; i++ ) {
    while ( L.ss > 1 && ccw( &v[L.s[L.ss-2]], &v[L.s[L.ss-1]], &v[i] ) >= 0 ) {
      L.ss--;
    }
    L.s[L.ss++] = i;
  }

  for ( i = N - 1; i >= 0; i-- ) {
    while ( U.ss > 1 && ccw( &v[U.s[U.ss-2]], &v[U.s[U.ss-1]], &v[i] ) >= 0 ) {
      U.ss--;
    }
    U.s[U.ss++] = i;
  }

  fout = fopen( "infasuratoare.out", "w" );
  L.ss--; U.ss--;
  fprintf( fout, "%d\n", L.ss + U.ss );
  for ( i = 0; i < L.ss; i++ ) {
    fprintf( fout, "%.10f %.10f\n", v[L.s[i]].x, v[L.s[i]].y );
  }
  for ( i = 0; i < U.ss; i++ ) {
    fprintf( fout, "%.10f %.10f\n", v[U.s[i]].x, v[U.s[i]].y );
  }
  fclose( fout );
  return 0;
}