Cod sursa(job #1701402)

Utilizator mihai995mihai995 mihai995 Data 12 mai 2016 23:18:57
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#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);
  }
};
istream& operator>>(istream& is, const Point& P) {
  is >> P.x >> P.y;
}
ostream& operator<<(ostream& os, const Point& P) {
  os << P.x << ' ' << P.y;
}
typedef vector<Point> Polygon;

Polygon 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();
    if ( i == poly.size() ) inc = -1;
  }
  hull.pop_back(); //remove duplicate of the first point
  return hull;
}

int main(){
  ifstream in("infasuratoare.in");
  ofstream out("infasuratoare.out");
  Polygon poly;
  Point P;
  int n;
  
  in >> n;
  while (n--){
    in >> P;
    poly.push_back(P);
  }
  poly = convexHull(poly);
  out << poly.size() << '\n';
  for (Point x : poly)
    out << x << '\n';
  return 0;
}