Cod sursa(job #1988381)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 2 iunie 2017 21:07:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;

FILE *in, *out;

int const nmax = 120000;

struct Point {
  double x;
  double y;

  bool operator<(Point other) const {
    if(x != other.x)
      return (x < other.x);
    else
      return (y < other.y);
  }
};

//|a.x a.y 1|
//|b.x b.y 1|
//|c.x c.y 1|
double det3(Point a, Point b, Point c) {
  double plus  = a.x * b.y + b.x * c.y + c.x * a.y;
  double minus = b.y * c.x + c.y * a.x + a.y * b.x;
  return (plus - minus);
}

int n;
Point v[1 + nmax];

Point sol[1 + nmax];
int nsol;

//pleci din a = v[1] in b si apoi in c si vezi ce intoarcere faci pe acest drum
bool cmp(Point b, Point c) {
  return (det3(v[1], b, c) < 0);
}

int main() {
  in = fopen("infasuratoare.in","r");
  out = fopen("infasuratoare.out","w");
  int n, imin = 1;
  fscanf(in, "%d", &n);
  for(int i = 1;i <= n;i ++) {
    fscanf(in, "%lf %lf", &v[i].x, &v[i].y);
    if(v[i] < v[imin])
      imin = i;
  }
  swap(v[1], v[imin]); //punctul care e sigur pe infasuratoare il punem in v[1]
  sort(v + 2, v + n + 1, cmp);

  nsol = 2;
  sol[1] = v[1];
  sol[2] = v[2];

  for(int i=3; i<=n; i++) {
    while(2 < nsol && det3(sol[nsol-1], sol[nsol], v[i]) >= 0)
      nsol--;
    sol[++nsol] = v[i];
  }

  /*
  for (int i = 3; i <= n; i++) {
    while (2 < nsol && (det3(sol[nsol - 1], sol[nsol], v[i]) > 0))
      nsol--;
    nsol++;
    sol[nsol] = v[i];
  }
  */
  fprintf(out, "%d\n", nsol);
  for(int i = nsol;i >= 1;i --){
    fprintf(out, "%.6lf %.6lf\n", sol[i].x, sol[i].y);
  }
  return 0;
}