Pagini recente » Cod sursa (job #467708) | Cod sursa (job #1273007) | Cod sursa (job #3270990) | Cod sursa (job #1993034) | Cod sursa (job #1701409)
#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;
}