Pagini recente » Cod sursa (job #246102) | Cod sursa (job #877108) | Cod sursa (job #2498284) | Cod sursa (job #502360) | Cod sursa (job #3210258)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
const int NMAX = 120005;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N;
struct Point {
long double x, y;
long double angle;
};
Point points[NMAX];
int hull[NMAX];
int H;
void read() {
fin >> N;
for (int i = 0; i < N; i++) {
fin >> points[i].x >> points[i].y;
}
}
bool is_counter_clockwise(Point a, Point b, Point c) {
return ((b.y - a.y) * (c.x - b.x) -
(b.x - a.x) * (c.y - b.y)) < 0;
}
void graham() {
hull[0] = 0;
hull[1] = 1;
H = 2;
for (int i = 2; i < N; i++) {
while (H >= 2 &&
!is_counter_clockwise(points[hull[H - 2]],
points[hull[H - 1]],
points[i])) {
H--;
}
hull[H++] = i;
}
}
int main()
{
read();
/// SOLVE 2 - Graham Scan (points.size() * log(points.size()))
for (int i = 1; i < N; i++) {
if (points[i].y < points[0].y) {
swap(points[i], points[0]);
}
}
points[0].angle = 0;
for (int i = 1; i <= N; i++) {
points[i].angle = atan2(points[i].y - points[0].y,
points[i].x - points[0].x);
}
sort(points + 1, points + N, [](Point a, Point b) {
return a.angle < b.angle;
});
graham();
fout << H << "\n";
for (int i = 0; i < H; i++) {
int idx = hull[i];
fout << fixed << setprecision(12) << points[idx].x << " ";
fout << fixed << setprecision(12) << points[idx].y << " ";
fout << "\n";
}
return 0;
}