Cod sursa(job #531922)

Utilizator andreitheo87Teodorescu Andrei-Marius andreitheo87 Data 10 februarie 2011 16:53:13
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <bitset>
#include <iostream>

using namespace std;

double EPS = 1e-12;

struct point{
  double x, y;
  int index;
  bool operator <(const point& other) const {
    if (labs(other.x-x) < EPS) return y < other.y;
    else return x < other.x;
  }
};

double double_area(point p1, point p2, point p3) {
  // p1.x  p1.y  1
  // p2.x  p2.y  1
  // p3.x  p3.y  1
  double area = p2.x*p3.y - p2.y*p3.x
    - (p1.x*p3.y - p1.y*p3.x)
    + (p1.x*p2.y - p1.y*p2.x);
  return area;
}

vector<point> convex_hull(vector<point>& vec, int n) {
  sort(vec.begin(), vec.end());
  for (int i=0; i<n; i++) {
    vec[i].index = i;
  }
  vector<point> rez;
  bitset<120001> used; // 25KB
  rez.push_back(vec[0]); used[0] = true;
  rez.push_back(vec[1]); used[1] = true;
  int siz = 2;
  for (int i=2; i<n; i++) {
    rez.push_back(vec[i]); siz++; used[i] = true;
    while (siz > 2 && double_area(rez[siz-3], rez[siz-2], rez[siz-1]) <= 0) {
      used[rez[siz-2].index] = false; rez[siz-2] = rez[siz-1]; siz--;
      rez.pop_back();
    }
  }
  for (int i=n-2; i>=1; i--) {
    if (!used[i]) {
      rez.push_back(vec[i]); siz++;
      while (siz > 2 && double_area(rez[siz-3], rez[siz-2], rez[siz-1]) <= 0) {
	rez[siz-2] = rez[siz-1]; siz--;
	rez.pop_back();
      }
    }
  }
  return rez;
}

int main() {
  freopen("infasuratoare.in", "r", stdin);
  freopen("infasuratoare.out", "w", stdout);
  int n;
  scanf("%d", &n);
  vector<point> vec(n);
  for (int i=0; i<n; i++) {
    scanf("%lf %lf", &vec[i].x, &vec[i].y);
  }
  vector<point> result = convex_hull(vec, n);
  printf("%d\n", result.size());
  for (int i=0; i<result.size(); i++) {
    printf("%.6lf %.6lf\n", result[i].x, result[i].y);
  }
  return 0;
}