Cod sursa(job #1817884)

Utilizator tudorcomanTudor Coman tudorcoman Data 28 noiembrie 2016 17:05:55
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxN = 120000;

class Point {
public:
  double x, y, panta;
  Point(double _x = 0, double _y = 0) : x(_x), y(_y) {
    panta = y / x;
  }
  inline bool operator < (const Point& other) const;
  pair<double, double> pereche() const {
    return make_pair(x, y);
  }
} v[maxN + 1], st[maxN + 1];;

inline double crossProduct(const Point& A, const Point& B, const Point& C) {
  return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

inline bool Point::operator < (const Point& other) const {
  return crossProduct(v[1], *this, other) < 0;
}

void sortV(int N) {
  int pos = 1;
  for(int i = 2; i <= N; ++ i)
    if(v[i].pereche() < v[pos].pereche())
      pos = i;
  swap(v[1], v[pos]);
  sort(v + 2, v + N + 1);
}

int top;

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

  int N;
  scanf("%d", &N);
  for(int i = 1; i <= N; ++ i)
    scanf("%lf %lf", &v[i].x, &v[i].y);

  sortV(N);

  st[++ top] = v[1];
  st[++ top] = v[2];

  for(int i = 3; i <= N; ++ i) {
    while(top >= 2 and crossProduct(st[top - 1], st[top], v[i]) > 0.0)
      -- top;
    st[++ top] = v[i];
  }

  printf("%d\n", top);
  for(int i = top; i; -- i)
    printf("%.9f %.9f\n", st[i].x, st[i].y);
  return 0;
}