Cod sursa(job #1380215)

Utilizator toranagahVlad Badelita toranagah Data 6 martie 2015 23:36:49
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
//Problem convexhull
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

#define x first
#define y second
#define mp make_pair
typedef pair<double, double> Point;

const int MAX_N = 120100;

int N;
Point points[MAX_N];
int hull[MAX_N];
int head = 0;

inline double xp(const Point &A, const Point &B, const Point &O = mp(0, 0)) {
  return ((A.x - O.x) * (B.y - O.y)) - ((A.y - O.y) * (B.x - O.x));
}

void convex_hull() {
  bool vis[MAX_N];

  hull[1] = 1;
  hull[2] = 2;
  vis[2] = true;
  head = 2;

  sort(points + 1, points + N + 1);

  for (int i = 3, p = 1; i > 0; i += p) {
    if (vis[i]) continue;
    while (head >= 2 && xp(points[hull[head]], points[i], points[hull[head - 1]]) < 0) {
      vis[hull[head]] = false;
      head -= 1;
    }
    head += 1;
    hull[head] = i;
    vis[i] = true;

    if (i == N) p = -p;
  }
  head -= 1;
}

int main() {
  fin >> N;
  for (int i = 1; i <= N; i += 1) {
    fin >> points[i].x >> points[i].y;
  }

  convex_hull();

  fout << fixed << setprecision(6);
  fout << head << '\n';
  for (int i = 1; i <= head; i += 1) {
    fout << points[hull[i]].x << ' ' << points[hull[i]].y << '\n';
  }
  return 0;
}