Pagini recente » Cod sursa (job #1789104) | Cod sursa (job #2310446) | Cod sursa (job #329667) | Cod sursa (job #429714) | Cod sursa (job #1198483)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
const int N = 1 + 1.2e5;
struct Point{
double x, y;
Point(double x = 0, double y = 0) : x(x), y(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) + A.cross(B) - cross(B);
}
inline bool operator<(const Point& P) const {
if (x != P.x)
return x < P.x;
return y < P.y;
}
};
Point P[N], aux[N];
int nrP;
void convexHull(Point P[], int& n){
sort(P + 1, P + n + 1);
int size = 0;
for (int i = 1, inc = 1 ; i ; i += inc){
while ( size > 1 && aux[ size - 1 ].cross( aux[size], P[i] ) < 0 )
size--;
aux[++size] = P[i];
if (i == n) inc = -1;
}
n = size - 1;
for (int i = 1 ; i <= n ; i++)
P[i] = aux[i];
}
int main(){
ifstream in("infasuratoare.in");
in >> nrP;
for (int i = 1 ; i <= nrP ; i++)
in >> P[i].x >> P[i].y;
in.close();
convexHull(P, nrP);
ofstream out("infasuratoare.out");
out << nrP << '\n';
out << setprecision(6) << fixed;
for (int i = 1 ; i <= nrP ; i++)
out << P[i].x << ' ' << P[i].y << '\n';
out.close();
return 0;
}