Cod sursa(job #2567993)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 3 martie 2020 20:04:35
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAX_N = 120000;
const double MAX_COORD = 1000000000;
const double INF = 2000000000;
const double eps = 1.e-12;

struct Point {
  double x;
  double y;
};

Point points[5 + MAX_N];
Point lowLeft;
Point st[5 + MAX_N];

double slope(Point a, Point b) {
  if (a.x == b.x)
    return INF;

  return (b.y - a.y) / (b.x - a.x);
}

bool cmp(Point a, Point b) {
  if (a.x == lowLeft.x && a.y == lowLeft.y)
    return true;
  if (b.x == lowLeft.x && b.y == lowLeft.y)
    return false;

  double sl1, sl2;
  sl1 = slope(lowLeft, a);
  sl2 = slope(lowLeft, b);

  if (sl1 >= -eps && sl2 < -eps)
    return true;
  else if (sl1 >= -eps)
    return sl1 - sl2 < -eps;
  else {
    if (sl2 >= -eps)
      return false;
    else
      return sl1 - sl2 < -eps;
  }

}

double area(Point a, Point b, Point c) {
  return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

bool trig(Point a, Point b, Point c) {
  return area(a, b, c) >= -eps;
}

int main() {
  freopen("infasuratoare.in", "r", stdin);
  freopen("infasuratoare.out", "w", stdout);

  int n;
  scanf("%d", &n);

  lowLeft.x = lowLeft.y = MAX_COORD + 1;
  for (int i = 1; i <= n; i++) {
    double x, y;
    scanf("%lf%lf", &x, &y);

    points[i] = {x, y};
    if (lowLeft.y > points[i].y || (lowLeft.y == points[i].y && lowLeft.x > points[i].x ))
      lowLeft = points[i];
  }

  sort(points + 1, points + n + 1, cmp);

  int sz;
  sz = 0;
  st[++sz] = points[1];
  st[++sz] = points[2];

  for (int i = 3; i <= n; i++) {
    while (!trig(st[sz - 1], st[sz], points[i]))
      sz--;

    st[++sz] = points[i];
  }

  printf("%d\n", sz);
  for (int i = 1; i <= sz; i++)
    printf("%f %f\n", st[i].x, st[i].y);

  return 0;
}