Cod sursa(job #1826628)

Utilizator GhiciCineRazvan Dumitriu GhiciCine Data 10 decembrie 2016 17:52:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <algorithm>

#define MAXN 120000

using namespace std;

struct POINT{
  double x, y;
}v[MAXN + 5];

int top1, top2;
int upper[MAXN + 5], lower[MAXN + 5];

bool cmp(POINT a, POINT b) {
  return a.x < b.x || ( a.x == b.x && a.y < b.y );
}

double ccw(POINT a, POINT b, POINT c) {
  return a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y;
}

int main(){
  FILE *f1, *f2;
  int n, i;

  f1 = fopen( "infasuratoare.in", "r" );
  f2 = fopen( "infasuratoare.out", "w" );

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

  for( i = 0; i < n; i++ ){
    fscanf( f1, "%lf%lf", &v[i].x, &v[i].y );
  }
  sort( v, v + n, cmp );
  top1 = 0;
  for( i = 0; i < n; i++ ){
    while( top1 >= 2 && ccw( v[i], v[lower[top1 - 1]], v[lower[top1 - 2]] ) > 0 ){
      top1--;
    }
    lower[top1] = i;
    top1++;
  }
  top2 = 0;
  for( i = 0; i < n; i++ ){
    while( top2 >= 2 && ccw( v[i], v[upper[top2 - 1]], v[upper[top2 - 2]] ) < 0 ){
      top2--;
    }
    upper[top2] = i;
    top2++;
  }
  fprintf( f2, "%d\n", top1 + top2 - 2 );
  for( i = 0; i < top1; ++i ) {
    fprintf( f2, "%lf %lf\n", v[lower[i]].x, v[lower[i]].y );
  }
  for( i = top2 - 2; i > 0; --i ) {
    fprintf( f2, "%lf %lf\n", v[upper[i]].x, v[upper[i]].y );
  }
  fclose( f1 );
  fclose( f2 );
  return 0;
}