Pagini recente » Cod sursa (job #2517070) | Borderou de evaluare (job #1036009) | Cod sursa (job #1658849) | Cod sursa (job #127825) | Cod sursa (job #2002851)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct Point { double x, y; };
int n, tr[120005], u;
Point v[120005];
int st[120005];
vector<int> sol;
const double eps = 1e-12;
inline double det(Point A, Point B, Point C) {
return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
}
bool ok() {
Point A = v[st[u - 2]];
Point B = v[st[u - 1]];
Point C = v[st[u]];
if (det(A, B, C) > 0) return true;
return false;
}
int main()
{
in >> n;
for (int i = 1; i <= n; ++i) {
in >> v[i].x >> v[i].y;
}
sort(v + 1, v + n + 1, [](Point a, Point b) -> bool {
if (a.x < b.x) return true;
if (a.x == b.x) return a.y < b.y;
return false;
});
st[++u] = 1;
st[++u] = 2;
for (int i = 3; i <= n; ++i) {
st[++u] = i;
while (!ok()) {
st[u-1] = st[u];
u--;
}
}
for (int i = 1; i <= u; ++i) {
sol.push_back(st[i]);
}
u = 0;
st[++u] = n;
st[++u] = n-1;
for (int i = n - 2; i >= 1; --i) {
st[++u] = i;
while (!ok()) {
st[u-1] = st[u];
u--;
}
}
for (int i = 2; i < u; ++i) {
sol.push_back(st[i]);
}
out << sol.size() << "\n";
for (int i = 0; i < sol.size(); ++i) {
out << fixed << setprecision(6) << v[sol[i]].x << " " << v[sol[i]].y << "\n";
}
return 0;
}