Cod sursa(job #1701409)

Utilizator mihai995mihai995 mihai995 Data 12 mai 2016 23:31:23
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;

struct Point{
	double x, y;
	Point(double x = 0, double y = 0) : x(x), y(y) {}

	inline bool operator<(const Point P) const {
		return x < P.x || (x == P.x && y < P.y);
	}
	inline double cross(const Point P) const {
		return x * P.y - y * P.x;
	}
  inline double cross(const Point A, const Point B) const {
    return cross(A) - cross(B) + A.cross(B);
  }
};
typedef vector<Point> Polygon;

void convexHull(Polygon& poly){
  sort( poly.begin(), poly.end() );

  Polygon hull;
  for (int i = 0, inc = 1; i >= 0; i += inc){
    while ( hull.size() > 1 && hull[ hull.size() - 2 ].cross( hull.back(), poly[i] ) < 0 )
      hull.pop_back();
    hull.push_back( poly[i] );
    if ( i == poly.size() ) inc = -1;
  }
  hull.pop_back(); //remove duplicate of the first point
  poly.swap(hull);
}

int main(){
  ifstream in("infasuratoare.in");
  ofstream out("infasuratoare.out");
  Polygon poly;
  double x, y;
  int n;

  in >> n;
  while (n--){
    in >> x >> y;
    poly.emplace_back(x, y);
  }
  convexHull(poly);
  out << poly.size() << '\n';
  out << setprecision(10) << fixed;
  for (Point x : poly)
    out << x.x << ' ' << x.y << '\n';
  return 0;
}