Cod sursa(job #1142646)

Utilizator nimeniaPaul Grigoras nimenia Data 14 martie 2014 00:09:43
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <deque>
#include <iomanip>

using namespace std;

pair<double, double> referencePoint;

bool compare (pair<double, double> a, pair<double, double> b) {

  /** In general, it's good to avoid division, to keep away from arithmetic errors.
      In this case, using the code below will lead to wrong results.
  */
  // double anglea = (a.second - referencePoint.second) / (a.first - referencePoint.first);
  // double angleb = (b.second - referencePoint.second) / (b.first - referencePoint.first);
  // return anglea < angleb;

  return
    (a.second - referencePoint.second) * (b.first - referencePoint.first) <
    (b.second - referencePoint.second) * (a.first - referencePoint.first);
}

bool going_left(pair<double, double> p1,
                pair<double, double> p2,
                pair<double, double> p3) {

  double res =
    (p2.first - p1.first) * (p3.second - p1.second) -
    (p2.second - p1.second) * (p3.first - p1.first);

  return
    (p2.first - p1.first) * (p3.second - p1.second) -
    (p2.second - p1.second) * (p3.first - p1.first) < 0;
}

ostream& operator << (ostream& os, const pair<double, double> &a) {
  os << "(" << a.first << ", " << a.second << ")";
  return os;
}

int main(int argc, char *argv[])
{

  ifstream f("infasuratoare.in");
  ofstream g("infasuratoare.out");
  double x, y;
  int n;

  f >> n;

  vector<pair<double, double> > polygon;

  double smallest_x = 123456789.0;
  double smallest_y = 123456789.0;

  for (int i = 0; i < n; i++) {
    f >> x >> y;
    polygon.push_back(make_pair(x, y));
    if (y < smallest_y || (y == smallest_y && x < smallest_x)) {
      smallest_y = y;
      smallest_x = x;
    }
  }

  referencePoint = make_pair(smallest_x, smallest_y);

  sort(polygon.begin(), polygon.end(), compare);

  vector<pair<double, double> > deq;
  deq.push_back(polygon[0]);
  deq.push_back(polygon[1]);

  int pos = 2;

  while (pos < n) {

    pair<double, double> next_point = polygon[pos++];
    pair<double, double> pp1 = deq[deq.size() - 1];
    pair<double, double> pp2 = deq[deq.size() - 2];

    while (!going_left(pp1, pp2, next_point)) {
      deq.pop_back();
      pp1 = deq[deq.size() - 1];
      pp2 = deq[deq.size() - 2];
    }

    deq.push_back(next_point);
  }

  g << fixed  << setprecision(6);
  g << deq.size() << endl;
  for (int i = 0; i < deq.size(); i++) {
    g << deq[i].first << " " << deq[i].second << endl;
  }

  return 0;
}