Pagini recente » Concursuri organizate de infoarena | Cod sursa (job #870135) | Cod sursa (job #561591) | Cod sursa (job #2880089) | Cod sursa (job #2476046)
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
struct Point
{
double x, y;
Point operator+(const Point& p) const {
return {x + p.x, y + p.y};
}
Point operator-() const {
return {-x, -y};
}
Point operator-(const Point& p) const {
return {x - p.x, y - p.y};
}
} v[120010], st[120010];
double cross(const Point& a, const Point& b)
{
return a.x * b.y - a.y * b.x;
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n;
cin >> n;
int leftbottomIdx = 0;
for(int i = 0; i < n; i++)
{
double a, b;
cin >> a >> b;
v[i].x = a;
v[i].y = b;
if(v[i].x < v[leftbottomIdx].x || (v[i].x == v[leftbottomIdx].x && v[i].y < v[leftbottomIdx].y))
leftbottomIdx = i;
}
swap(v[0], v[leftbottomIdx]);
sort(v + 1, v + n, [](const Point& a, const Point& b) {
return cross(a - v[0], b - v[0]) >= 0;
});
int lst = 2;
st[0] = v[0];
st[1] = v[1];
for(int i = 2; i < n; i++)
{
while(lst >= 2 && cross(st[lst - 1] - st[lst - 2], v[i] - st[lst - 1]) <= 0)
lst--;
st[lst++] = v[i];
}
cout << lst << '\n';
for(int i = 0; i < lst; i++)
{
cout << fixed << setprecision(12) << st[i].x << ' ' << fixed << setprecision(12) << st[i].y << '\n';
}
return 0;
}