Cod sursa(job #1043232)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 28 noiembrie 2013 09:49:49
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

class point{
public:
  double x, y;

  point(){};

  point(double x1, double y1){
    x = x1;
    y = y1;
  }

  bool operator ==(point other){
    return (x == other.x && y == other.y);
  }
};

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

double ccw(point A, point B, point C){
  return 0.5 * (C.y * (B.x - A.x) + B.y * (A.x - C.x) + A.y * (C.x - B.x)); //C at the left of AB is positive, else negative.
}

vector<point> gv;
point refr;

int n;

int cmp(point x, point y){
  if(y == refr)
    return 0;
  if(x == refr)
    return 1;

  if(ccw(refr, x, y) == 0){
    return dist(refr, y) > dist(refr, x);
  }

  return (ccw(refr, x, y) >= 0);
}

int main(){
  ifstream in("infasuratoare.in");
  ofstream out("infasuratoare.out");

  in >> n;

  for(int i = 1; i <= n; ++i){
    double x, y;
    in >> x >> y;
    gv.push_back(point(x, y));
  }

  int best = 0;

  for(int i = 1; i < gv.size(); ++i)
    if(gv[i].x < gv[best].x)
      best = i;
    else if(gv[i].y < gv[best].y && gv[i].x == gv[best].x)
      best = i;

  swap(gv[0], gv[best]);
  refr = gv[0];

  sort(gv.begin(), gv.end(), cmp);

  for(int i = n - 2; i > 0; --i)
    if(ccw(gv[i], gv[i + 1], refr) != 0){
      for(int j = i + 1, k = n - 1; j < k; ++j, --k)
        swap(gv[j], gv[k]);
      break;
    }

  gv.push_back(gv[0]);

  vector<int> hull;
  int u = 0;

  hull.push_back(0);
  ++u;

  for(int i = 1; i <= n; ++i){
    hull.push_back(i);
    ++u;
    while(u >= 3)
      if(ccw(gv[hull[u - 3]], gv[hull[u - 2]], gv[hull[u - 1]]) < 0){
        hull[u - 2] = hull[u - 1];
        hull.pop_back();
        --u;
      }
      else
        break;
  }

  hull.pop_back();
  --u;

  out << u << "\n";
  for(int i = 0; i < u; ++i)
    out << setprecision(12) << gv[hull[i]].x << " " << gv[hull[i]].y << "\n";

  return 0;
}