Cod sursa(job #717790)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 20 martie 2012 11:08:12
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.5 kb
/**
  lower hull and upper hull algorithm
**/

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

#include<vector>
#include<algorithm>

using namespace std;

class point{
public :
  double x, y;

  point(){};

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

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

bool operator < (point one, point other){
  return one.x < other.x;
}

const int knmax = 120005;
point given[knmax];
int points;
vector<int> index_up, index_down;

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;
}

int solve_stack(vector<int>::iterator it, double cof, int size){
  int r_val = 0;

  while(size >= 3 && (cof * ccw(given[*(it - 2)], given[*(it - 1)], given[*it])) >= 0){
    --size;
    ++r_val;
    *(it - 1) = *it;
    --it;
  }

  return r_val;
}

void solve(){
  sort(given + 1, given + points + 1);
  // get the start and the end

  index_up.push_back(1);
  index_down.push_back(1);
  // the start point

  int j;
  for(int i = 2; i <= points; ++i){
    double aux = ccw(given[1], given[points], given[i]);

    if(aux <= 0){
      index_up.push_back(i);
      j = solve_stack(index_up.end() - 1, -1.0, index_up.size());
      while(j){
        --j;
        index_up.pop_back();
      }
    }

    if(aux >= 0){
      index_down.push_back(i);
      j = solve_stack(index_down.end() - 1, 1.0, index_down.size());
      while(j){
        --j;
        index_down.pop_back();
      }
    }
  }
  // the hull algorithm, notice it is a lot easier to code than the graham scan
  // because the complexity of the algorithms is given by the sorting of the points
  // this one is faster because we have a smaller constant in sorting

}

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

  printf("%d\n", index_up.size() + index_down.size() - 2);
  //number of points in the hull, decreasing 2 because end and start are counted twice

  for(vector<int>::iterator it = index_up.begin(); it < index_up.end(); ++it)
    printf("%lf %lf\n", given[*it].x, given[*it].y);

  for(vector<int>::iterator it = index_down.end() - 2; it > index_down.begin(); --it)
    printf("%lf %lf\n", given[*it].x, given[*it].y);
}

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