Pagini recente » Borderou de evaluare (job #1151831) | Borderou de evaluare (job #2050251) | Cod sursa (job #3359619) | Cod sursa (job #3359618) | Cod sursa (job #3359639)
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
#define ld long double
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 12e4 + 5;
struct Point {
ld x, y;
};
Point o = {0.0, 0.0};
ld dist(Point a, Point b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
ld crossproduct(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(const Point &a, const Point &b) {
ld prod = crossproduct(o, a, b);
if (prod == 0)
return dist(o, a) < dist(o, b);
return prod > 0;
}
Point v[NMAX];
int main() {
int n;
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> v[i].x >> v[i].y;
}
int lowest = 1;
for (int i = 2; i <= n; i++) {
if (v[i].y < v[lowest].y ||
v[i].y == v[lowest].y && v[i].x < v[lowest].x)
lowest = i;
}
swap(v[1], v[lowest]);
o = v[1];
sort(v + 2, v + n + 1, cmp);
vector<Point> hull;
hull.push_back(v[1]);
for (int i = 2; i <= n; i++) {
while (hull.size() >= 2 &&
crossproduct(hull[hull.size() - 2], hull.back(), v[i]) <= 0)
hull.pop_back();
hull.push_back(v[i]);
}
fout << hull.size() << '\n';
fout << fixed << setprecision(12);
for (auto it : hull) {
fout << it.x << ' ' << it.y << '\n';
}
return 0;
}