Cod sursa(job #717668)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 20 martie 2012 09:46:33
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 kb
/**
  graham scan convex hull
**/

#include<stdio.h>
#include<assert.h>
#include<math.h>

#include<algorithm>
#include<vector>

using namespace std;

double minx, miny;

class point{
public:
  double x, y;

  point(){};

  double dist(point other){
    return sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
  }

  friend bool operator < (point one, point other);
};

bool operator< (point one, point other){
    double slope_other = (other.y - miny) / (other.x - minx);
    double slope_here = (one.y - miny) / (one.x - minx);
    if(slope_other == slope_here){
      point aux;
      aux.x = minx;
      aux.y = miny;
      return one.dist(aux) < other.dist(aux);
    }
    return !(slope_here < slope_other);
}

const int knmax = 120005;
const double keps = 0.000000001;
int points;
vector<int> index_stack;
point given[120005];

void read(){
  assert(freopen("infasuratoare.in", "r", stdin) != NULL);

  scanf("%d", &points);

  for(int i = 1; i <= points; ++i)
    scanf("%lf%lf", &given[i].x, &given[i].y);
}

double ccw(point one, point two, point three){
  return ((two.y - three.y) * (one.x - two.x) - (two.x - three.x) * (one.y - two.y)) / 2;
}

bool must_decrease(){
  if(index_stack.size() < 3)
    return false; // we cannot remove any point from the stack
  vector<int>::iterator it = index_stack.end() - 1;
  return (ccw(given[*(it - 2)], given[*(it - 1)], given[*it]) > 0);
}

void solve(){
  for(int i = 2; i <= points; ++i)
    if(given[i].x < given[1].x)
      swap(given[1], given[i]);
    else if(given[i].y < given[1].y && given[i].x == given[1].x)
      swap(given[1], given[i]);
  minx = given[1].x;
  miny = given[1].y;
  // get certain point

  sort(given + 2, given + points + 1);
  // sort after slope, the < operator is overloaded
  given[++points] = given[1];
  // add first point at the end to ensure the corect hull

  index_stack.push_back(1);

  for(int i = 2; i <= points; ++i){
    index_stack.push_back(i);
    while(must_decrease()){
      index_stack.pop_back();
      index_stack.back() = i;
    }
  }
  // we have the hull

  index_stack.pop_back();
  //remove the first element from the end of the stack
}

void write(){
  assert(freopen("infasuratoare.out", "w", stdout) != NULL);

  printf("%d\n", index_stack.size());
  for(vector<int>::iterator it = index_stack.end() - 1; it >= index_stack.begin(); --it)
    printf("%lf %lf\n", given[*it].x, given[*it].y);
  //output the hull
}

int main(){
  read();
  solve();
  write();
  return 0;
}