Cod sursa(job #1143048)

Utilizator nimeniaPaul Grigoras nimenia Data 14 martie 2014 16:56:21
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.59 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) {
  return
    (p2.first - p1.first) * (p3.second - p2.second) -
    (p2.second - p1.second) * (p3.first - p2.first) > 0;
}

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

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

  double x, y;
  int n;

  FILE* fin = fopen("infasuratoare.in", "r");
  FILE* fout = fopen("infasuratoare.out", "w");
  fscanf(fin, "%d", &n);

  vector<pair<double, double> > polygon;

  double smallest_x, smallest_y;
  bool first = true;

  for (int i = 0; i < n; i++) {
    fscanf(fin, "%lf %lf", &x, &y);
    if (first || x < smallest_x || (x == smallest_x && y < smallest_y)) {
      if (!first)
	polygon.push_back(make_pair(smallest_x, smallest_y));
      smallest_y = y;
      smallest_x = x;
      first = false;
    } else {
      polygon.push_back(make_pair(x, y));
    }
  }

  referencePoint = make_pair(smallest_x, smallest_y);

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

  // for (int i = 0; i < n; i++) {
  //   cout << polygon[i] << " ";
  // }

  vector<pair<double, double> > deq;

  deq.push_back(referencePoint);
  deq.push_back(polygon[0]);

  int pos = 1;

  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(pp2, pp1, next_point)) {
      deq.pop_back();
      pp1 = deq[deq.size() - 1];
      pp2 = deq[deq.size() - 2];
    }

    deq.push_back(next_point);
  }

  fprintf(fout, "%d\n", deq.size() - 1);
  for (int i = 0; i < deq.size() - 1; i++) {
    fprintf(fout, "%.6lf %.6lf\n",
	    deq[i].first,
	    deq[i].second);
  }

  return 0;
}