Cod sursa(job #1659174)

Utilizator thewildnathNathan Wildenberg thewildnath Data 22 martie 2016 00:53:28
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <algorithm>
#include <cstdio>
#include <cmath>
//#include <set>

using namespace std;

struct punct {
  double x;
  double y;
  double unghi;

  punct(const double &x = 0, const double &y = 0) {
    this->x = x;
    this->y = y;
  }

  punct operator += (const punct &arg) {
    this->x += arg.x;
    this->y += arg.y;
    return *this;
  }

  punct operator -= (const punct &arg) {
    this->x -= arg.x;
    this->y -= arg.y;
    return *this;
  }

  bool operator < (const punct &arg) const {
    return this->unghi < arg.unghi;
  }
};

const int NMAX = 120000;
const double EPS = 1e-8;

int N, M;

punct centru;
punct pct[1 + NMAX];
punct stiva[1 + NMAX];

//set <punct> st;

inline double cross_product(const punct &o, const punct &a, const punct &b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

void infas() {
  sort(pct + 1, pct + 1 + N);

  int num = 0;

  for (int i = 1; i <= N; ++i) {
      while (num >= 2 && cross_product(stiva[num - 1], stiva[num], pct[i]) <= EPS)
          --num;
      stiva[++num] = pct[i];
  }
  if (num > 2 && cross_product(stiva[num - 1], stiva[num], stiva[1]) <= EPS)
    --num;

  printf("%d\n", num);
  for (int i = 1; i <= num; ++i)
    printf("%f %f\n", stiva[i].x + centru.x, stiva[i].y + centru.y);
}

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

  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) {
    scanf("%lf%lf", &pct[i].x, &pct[i].y);
    centru += pct[i];
  }
  centru.x /= N;
  centru.y /= N;
  for (int i = 1; i <= N; ++i) {
    pct[i] -= centru;
    pct[i].unghi = atan2(pct[i].y, pct[i].x);
  }

  infas();

  return 0;
}