Cod sursa(job #1469128)

Utilizator hrazvanHarsan Razvan hrazvan Data 7 august 2015 16:53:00
Problema Infasuratoare convexa Scor 50
Compilator c Status done
Runda Arhiva educationala Marime 1.96 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 120000
#define INF 2000000000
#define EPS 0.00000000000001
double x[MAXN], y[MAXN];
int st[MAXN];
double mx = INF * 1.0, my = INF * 1.0;

inline double aria(int p1, int p2, int p3){
  return (x[p2] - x[p1]) * (y[p3] - y[p1]) - (x[p3] - x[p1]) * (y[p2] - y[p1]);
}

inline double modul(double x){
  return x < 0.0 ? -x : x;
}

inline char eq(double x, double y){
  long long p = 1, nr = 0;
  while(nr < 12 && modul(x) / 10 >= p * 1.0 || modul(y) / 10 >= p * 1.0){
    p *= 10;
    nr++;
  }
  if(x - y < -EPS * p)
    return -1;
  if(x - y > -EPS * p && x - y < EPS * p)
    return 0;
  return 1;
}

void qs(int st, int dr){
  int i = st, j = dr, pv = st + rand() % (dr - st + 1);
  double px = x[pv] - mx, py = y[pv] - my, aux;
  while(i <= j){
    while(eq((y[i] - my) * px, (x[i] - mx) * py) == -1)
      i++;
    while(eq((y[j] - my) * px, (x[j] - mx) * py) == 1)
      j--;
    if(i <= j){
      aux = x[i];  x[i] = x[j];  x[j] = aux;
      aux = y[i];  y[i] = y[j];  y[j] = aux;
      i++;  j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

int main(){
  srand(time(NULL));
  FILE *in = fopen("infasuratoare.in", "r");
  int n, i, p;
  double aux;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++){
    fscanf(in, "%lf%lf", &x[i], &y[i]);
    if(eq(mx, x[i]) == 1 || (eq(mx, x[i]) == 0 && eq(my, y[i]) == 1)){
      mx = x[i];
      my = y[i];
      p = i;
    }
  }
  aux = x[p];  x[p] = x[0];  x[0] = aux;
  aux = y[p];  y[p] = y[0];  y[0] = aux;
  fclose(in);
  qs(1, n - 1);
  int dr = 2;
  st[0] = 0;  st[1] = 1;
  for(i = 2; i < n; i++){
    while(eq(aria(st[dr - 2], st[dr - 1], i), 0) == -1)
      dr--;
    st[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", x[st[i]], y[st[i]]);
  fclose(in);
  return 0;
}