Cod sursa(job #2155503)

Utilizator stoianmihailStoian Mihail stoianmihail Data 7 martie 2018 21:32:47
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <stdio.h>
#include <climits>
#include <cmath>
#include <algorithm>

using std::sort;

struct point {
  double x, y;
  double ang;

  point() {
    this -> x = this -> y = 0;
    this -> ang = 0;
  }

  point(float x, float y) {
    this -> x = x;
    this -> y = y;
  }
};

#define MAX_N 120000

const double EPS = 1e-12;
const double pi = 3.141592654;

int N, ss;
point p[MAX_N + 1];
point stack[MAX_N + 1];
point min = point(INT_MAX, INT_MAX);

double MOD(double X) {
  if (X > EPS) {
    return X;
  }
  return -X;
}

double ccw(point p1, point p2, point p3) {
  return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}

double get(point curr) {
  double ret = atan2(curr.y, curr.x);
  if (curr.y >= -EPS) {
    return ret;
  }
  return 2 * pi + ret;
}

bool cmp(point a, point b) {
  if (ccw(min, a, b) > EPS) {
    return 1;
  } else if (MOD(ccw(min, a, b)) < EPS) {
    return EPS < b.x - a.x;
  }
  //return (b.ang - a.ang > -EPS) || ((MOD(b.ang - a.ang) < EPS) && (-EPS < MOD(b.x) - MOD(a.x)));
}

int main(void) {
  FILE *f = fopen("infasuratoare.in", "r");

  int i, pos = 0;
  fscanf(f, "%d", &N);
  for (i = 1; i <= N; i++) {
    fscanf(f, "%lf %lf", &p[i].x, &p[i].y);
    if (p[i].y < min.y) {
      pos = i;
      min = p[i];
    } else if (p[i].y == min.y && p[i].x < min.x) {
      min = p[i];
      pos = i;
    }
  }
  fclose(f);

  point tmp = p[1];
  p[1] = min;
  p[pos] = tmp;
  sort(p + 2, p + N + 1, cmp);

  for (i = 1; i <= N; i++) {
    fprintf(stderr, "%lf %lf\n", p[i].x, p[i].y);
  }

  stack[ss++] = p[1];
  stack[ss++] = p[2];
  for (i = 3; i <= N; i++) {
    while (ss > 2 && ccw(stack[ss - 2], stack[ss - 1], p[i]) < -EPS) {
      ss--;
    }
    stack[ss++] = p[i];
  }

  freopen("infasuratoare.out", "w", stdout);
  fprintf(stdout, "%d\n", ss);
  for (i = 0; i < ss; i++) {
    fprintf(stdout, "%lf %lf\n", stack[i].x, stack[i].y);
  }
  fclose(stdout);
  return 0;
}