Cod sursa(job #1959861)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 9 aprilie 2017 23:36:54
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX_N = 120000;

struct Point {
  double x;
  double y;
  
  Point (int _x = INT_MAX, int _y = INT_MAX): x(_x), y(_y) {}
}bottom;

vector<Point> v;
int st[5 + MAX_N];


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

int ccw(Point a, Point b, Point c) {
  double cp = cross_product(a, b, c);
  if (cp == 0)
    return 0;
  if (cp < 0)
    return -1;
  return 1;
}

int dist(Point a, Point b) {
  return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

bool cmp(Point a, Point b) {
  int cp = ccw(bottom, a, b);
  if (cp == 0)
    return dist(bottom, a) < dist(bottom, b);
  if (cp == -1)
    return false;
  return true;
}

int main() {
  freopen("infasuratoare.in", "r", stdin);
  freopen("infasuratoare.out", "w", stdout);
  
  int N, poz = 0;
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    double x, y;
    Point p;
    scanf("%lf%lf", &x, &y);
    p.x = x;
    p.y = y;
    if (bottom.y > y) {
      bottom = p;
      poz = i;
    } else if (bottom.y == y && bottom.x > x) {
      bottom = p;
      poz = i;
    }
    v.push_back(p);
  }
  swap(v[poz], v[0]);
  sort(v.begin() + 1, v.end(), cmp);
  v.push_back(v[0]);
  st[0] = 0;
  st[1] = 1;
  int ind = 2, top = 1;
  while (ind < v.size()) {
    int cp = ccw(v[st[top - 1]], v[st[top]], v[ind]);
    if (cp == 0) {
      st[top] = ind++;
    } else if (cp == 1) {
      st[++top] = ind++;
    } else {
      --top;
    }
  }
  printf("%d\n", top);
  for (int i = 0; i < top; ++i) {
    printf("%.13lf %.13lf\n", v[st[i]].x, v[st[i]].y);
  }
  return 0;
}