Cod sursa(job #2437121)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 8 iulie 2019 16:11:20
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <algorithm>

#define NMAX 120000

using namespace std;

struct Point {
  double x ;
  double y ;
};

class Stiva {
  public:
  int top ;
  Point v [ NMAX + 1 ] ;
  Stiva () {
    top = 0 ;
  }
  void push (Point x ) {
    v[top++] = x ;
  }
  void pop () {
    top--;
  }
};

Point v [ NMAX + 1 ] ;
Stiva st ;

float difpant (Point A, Point B, Point C ) {
  return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x) ;
}

bool cmp2 (Point A, Point B ) {
  if (A.y < B.y )
    return true ;
  else if (A.y == B.y && A.x < B.x )
    return true ;
  return false ;
}

bool cmp1 (Point A, Point B ) {
  return difpant(v[0], A, B ) < 0 ;
}

int main() {

  FILE *fin, *fout ;
  fin = fopen ("infasuratoare.in", "r" ) ;
  fout = fopen ("infasuratoare.out", "w" ) ;
  int n, i ;
  fscanf (fin, "%d", &n ) ;
  for (i = 0 ; i < n ; i++ )
    fscanf (fin, "%lf%lf", &v[i].x, &v[i].y ) ;
  sort(v, v+n, cmp2 ) ;
  sort(v+1, v+n, cmp1 ) ;
  st.push(v[0]) ;
  st.push(v[1]) ;
  i = 2 ;
  while ( i < n ) {
    while (st.top > 0 && difpant(st.v[st.top-2], st.v[st.top-1], v[i]) > 0 )
      st.pop() ;
    st.push(v[i]) ;
    i++;
  }
  fprintf (fout, "%d\n", st.top ) ;
  for (i = 0 ; i < st.top ; i++ )
    fprintf (fout, "%.6f %.6f\n", st.v[i].x, st.v[i].y ) ;
  return 0;
}