Cod sursa(job #1822769)

Utilizator TincaMateiTinca Matei TincaMatei Data 5 decembrie 2016 15:49:45
Problema Infasuratoare convexa Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <algorithm>

const int MAX_N = 120000;
struct Punct {
  double x, y;
}v[MAX_N];

int top1, top2;
int upper[MAX_N];
int lower[MAX_N];

bool cmp(Punct a, Punct b) {
  return a.x < b.x;
}

double ccw(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;
}

int main() {
  int n;
  FILE *fin = fopen("infasuratoare.in", "r");
  fscanf(fin, "%d", &n);
  for(int i = 0; i < n; ++i)
    fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
  fclose(fin);

  std::sort(v, v + n, cmp);
  top1 = 0;
  for(int 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(int 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++;
  }

  FILE *fout = fopen("infasuratoare.out", "w");
  fprintf(fout, "%d\n", top1 + top2 - 2);
  for(int i = 0; i < top1; ++i)
    fprintf(fout, "%lf %lf\n", v[lower[i]].x, v[lower[i]].y);
  for(int i = top2 - 2; i > 0; --i)
    fprintf(fout, "%lf %lf\n", v[upper[i]].x, v[upper[i]].y);
  fclose(fout);
  return 0;
}