Pagini recente » Cod sursa (job #1702946) | Cod sursa (job #3187345) | Cod sursa (job #3277218) | Cod sursa (job #1441646) | Cod sursa (job #2208839)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef pair<double, double> point;
vector<point> v;
int n, m, szt, szb;
set<point> top, bot;
double det(point a, point b, point c) {
return a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y;
}
void CHull(vector<point> v) {
sort(v.begin(), v.end());
for (auto p: v) {
while (szt >= 2 && det(*prev(prev(top.end())), *prev(top.end()), p) >= 0)
top.erase(prev(top.end())), --szt;
top.insert(p);
++szt;
while (szb >= 2 && det(*prev(prev(bot.end())), *prev(bot.end()), p) <= 0)
bot.erase(prev(bot.end())), --szb;
bot.insert(p);
++szb;
}
}
int main()
{
f >> n;
for (int i = 1; i <= n; ++i) {
double x, y;
f >> x >> y;
v.push_back({x, y});
}
CHull(v);
g << szt + szb - 2 << '\n';
for (auto a: bot) g << fixed << setprecision(10) << a.x << ' ' << a.y << '\n';
auto it = prev(top.end());
while (it != next(top.begin()) && it != top.begin()) {
--it;
g << fixed << setprecision(10) << it->x << ' ' << it->y << '\n';
}
return 0;
}