Cod sursa(job #1545863)

Utilizator hrazvanHarsan Razvan hrazvan Data 7 decembrie 2015 11:36:50
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <cstdio>
#include <algorithm>
#define MAXN 120000
#define INF 2000000000000000.0
#define EPS 0.0000000001

typedef struct{
  double x, y;
}punct;

int sv[MAXN];
punct v[MAXN];

inline char eq(double a, double b){
  if(a - b > EPS)
    return 1;
  if(a - b < -EPS)
    return -1;
  return 0;
}

inline double aria(punct a, punct b, punct 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;
}

inline int cmp(punct x, punct y){
  return aria(v[0], x, y) > 0;
}

void qs(int st, int dr){
  int i = st, j = dr;
  punct piv = v[(st + dr) / 2], aux;
  while(i <= j){
    while(cmp(piv, v[i]) == 1)
      i++;
    while(cmp(v[j], piv) == 1)
      j--;
    if(i <= j){
      aux = v[i];  v[i] = v[j];  v[j] = aux;
      i++;  j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

int main(){
  FILE *in = fopen("infasuratoare.in", "r");
  int n, i, p;
  punct m;
  m.x = INF;  m.y = INF;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++){
    fscanf(in, "%lf%lf", &v[i].x, &v[i].y);
    if(eq(m.x, v[i].x) == 1){
      m = v[i];
      p = i;
    }
    else  if(eq(m.x, v[i].x) == 0 && eq(m.y, v[i].y) == 1){
      m = v[i];
      p = i;
    }
  }
  fclose(in);
  punct aux;
  aux = v[p];  v[p] = v[0];  v[0] = aux;
  std::sort(v + 1, v + n, cmp);
  sv[0] = 0;
  sv[1] = 1;
  int dr = 2;
  for(i = 2; i < n; i++){
    while(dr > 2 && eq(aria(v[sv[dr - 2]], v[sv[dr - 1]], v[i]), 0) == -1)
      dr--;
    sv[dr] = i;
    dr++;
  }
  FILE *out = fopen("infasuratoare.out", "w");
  fprintf(out, "%d\n", dr);
  for(i = 0; i < dr; i++)
    fprintf(out, "%lf %lf\n", v[sv[i]].x, v[sv[i]].y);
  fclose(out);
  return 0;
}