Pagini recente » Cod sursa (job #450534) | Cod sursa (job #446702) | Cod sursa (job #21231) | Cod sursa (job #619875) | Cod sursa (job #1701403)
#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;
return is;
}
ostream& operator<<(ostream& os, const Point& P) {
os << P.x << ' ' << P.y;
return os;
}
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;
}