Cod sursa(job #3233064)

Utilizator Traian_7109Traian Mihai Danciu Traian_7109 Data 2 iunie 2024 13:09:21
Problema Infasuratoare convexa Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <stdio.h>

#define MAXN 120000
#define MAXY 1000000000
#define EPSILON 0.000000000001

long double x[MAXN], y[MAXN];
char viz[MAXN];
int stiva[MAXN];

static inline int compare(int a, int b) {
  if (x[a] == x[b])
    return y[a] < y[b];
  return x[a] < x[b];
}

void myqsort(int begin, int end) {
  int b = begin - 1, e = end + 1, pivot = (begin + end) / 2;
  long double aux;
  while (compare(++b, pivot));
  while (compare(pivot, --e));
  while (b < e) {
    aux = x[b];
    x[b] = x[e];
    x[e] = aux;
    aux = y[b];
    y[b] = y[e];
    y[e] = aux;
    while (compare(++b, pivot));
    while (compare(pivot, --e));
  }
  if (begin < e)
    myqsort(begin, e);
  if (e + 1 < end)
    myqsort(e + 1, end);
}

static inline long double det(int a, int b, int c) {
  return x[a] * (y[b] - y[c]) + x[b] * (y[c] - y[a]) + x[c] * (y[a] - y[b]);
}

int main() {
  FILE *fin, *fout;
  int n, i, sp, oldsp;
  fin = fopen("infasuratoare.in", "r");
  fscanf(fin, "%d", &n);
  for (i = 0; i < n; i++)
    fscanf(fin, "%Lf%Lf", &x[i], &y[i]);
  fclose(fin);
  myqsort(0, n - 1);
  sp = 0;
  for (i = 0; i < n; i++) {
    while (sp > 1 && det(stiva[sp - 1], stiva[sp - 2], i) < EPSILON)
      sp--;
    stiva[sp++] = i;
  }
  oldsp = sp;
  for (i = n - 1; i >= 0; i--) {
    while (sp > oldsp && det(stiva[sp - 1], stiva[sp - 2], i) < EPSILON)
      sp--;
    stiva[sp++] = i;
  }
  sp--;
  fout = fopen("infasuratoare.out", "w");
  fprintf(fout, "%d\n", sp);
  for (i = 0; i < sp; i++)
    fprintf(fout, "%.12Lf %.12Lf\n", x[stiva[i]], y[stiva[i]]);
  fclose(fout);
  return 0;
}