Pagini recente » Cod sursa (job #3344197) | Cod sursa (job #138933) | Cod sursa (job #74718) | Cod sursa (job #2129661) | Cod sursa (job #3336865)
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast", "unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
#define int ll
using pii = pair<int, int>;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 67;
const int MAXN = 1e5 + 5;
int ox, oy;
struct point
{
ld x, y;
};
vector<point> v;
ld det(point a, point b, point c)
{
return (a.x * b.y - a.y * b.x) + (b.x * c.y - b.y * c.x) + (c.x * a.y - c.y * a.x);
}
vector<point> hull(vector<point> v)
{
vector<point> up, dw;
sort(v.begin(), v.end(), [&](point a, point b){
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
});
for(point p : v)
{
while(up.size() >= 2 && det(up[up.size() - 2], up[up.size() - 1], p) >= 0)
{
up.pop_back();
}
up.push_back(p);
}
for(point p : v)
{
while(dw.size() >= 2 && det(dw[dw.size() - 2], dw[dw.size() - 1], p) <= 0)
{
dw.pop_back();
}
dw.push_back(p);
}
dw.pop_back();
reverse(up.begin(), up.end());
up.pop_back();
for(point p : up)
dw.push_back(p);
return dw;
}
ld dist(point a, point b)
{
return sqrtl((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<point> v;
for(int i = 1; i <= n; i++)
{
ld x, y;
cin >> x >> y;
v.push_back({x, y});
}
if(n == 1)
{
for(auto [x, y] : v)
{
cout << fixed << setprecision(12) << x << ' ' << y << '\n';
}
return 0;
}
v = hull(v);
cout << v.size() << '\n';
for(auto [x, y] : v)
{
cout << fixed << setprecision(12) << x << ' ' << y << '\n';
}
return 0;
}