Pagini recente » Cod sursa (job #1759519) | Cod sursa (job #353034) | Cod sursa (job #1815619) | Profil Djok | Cod sursa (job #1380208)
//Problem convexhull
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define x first
#define y second
#define mp make_pair
typedef pair<double, double> Point;
const int MAX_N = 120100;
int N;
Point points[MAX_N];
int hull[MAX_N];
int head = 0;
inline double xp(const Point &A, const Point &B, const Point &O = mp(0, 0)) {
return ((A.x - O.x) * (B.y - O.y)) - ((A.y - O.y) * (B.x - O.x));
}
void convex_hull() {
bool vis[MAX_N];
hull[head += 1] = 1;
hull[head += 1] = 2;
vis[1] = vis[2] = true;
sort(points + 1, points + N + 1);
for (int i = 3, p = 1; i > 0; i += p) {
if (vis[i]) continue;
while (head >= 2 && xp(points[hull[head]], points[i], points[hull[head - 1]]) < 0) {
vis[hull[head]] = false;
head -= 1;
}
hull[head += 1] = i;
vis[i] = true;
if (i == N) p = -p;
}
}
int main() {
fin >> N;
for (int i = 1; i <= N; i += 1) {
fin >> points[i].x >> points[i].y;
}
convex_hull();
fout << setprecision(12);
fout << head << '\n';
for (int i = 1; i <= head; i += 1) {
fout << points[hull[i]].x << ' ' << points[hull[i]].y << '\n';
}
return 0;
}