Pagini recente » Cod sursa (job #1828179) | Cod sursa (job #1406097) | Cod sursa (job #2266490) | Cod sursa (job #2400821) | Cod sursa (job #3229072)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 120002
#define eps 1e-12
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
class Point {
public:
double x, y;
Point(){}
Point(double x, double y) {
this->x = x;
this->y = y;
}
bool operator< (const Point& A) const {
if (abs(this->x - A.x) < eps)
return this->y < A.y;
return this->x < A.x;
}
};
vector<Point> points;
double det(const Point& A, const Point& B, const Point& C) {
return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
}
Point Hull[NMAX];
int ConvexHull(const int N) {
int L = 0;
for (int i = 1; i <= N; ++i) {
while (L > 1 && det(Hull[L - 1], Hull[L], points[i]) <= 0)
L--;
Hull[++L] = points[i];
}
int l = L;
for (int i = N; i >= 1; --i) {
while (L > l && det(Hull[L - 1], Hull[L], points[i]) <= 0)
L--;
Hull[++L] = points[i];
}
L--;
return L;
}
int main() {
int N;
fin >> N;
points.resize(N + 2);
for (int i = 1; i <= N; ++i)
fin >> points[i].x >> points[i].y;
sort(points.begin() + 1, points.begin() + N + 1);
int nrP = ConvexHull(N);
fout << nrP << "\n";
for (int i = 1; i <= nrP; ++i)
fout << fixed << setprecision(7) << Hull[i].x << " " << Hull[i].y << "\n";
return 0;
}