Pagini recente » Cod sursa (job #303153) | Cod sursa (job #843276) | Cod sursa (job #528237) | Cod sursa (job #2121787) | Cod sursa (job #3032923)
/// [A][M][C][B][N] ///
#include <bits/stdc++.h>
const char nl = '\n';
const char sp = ' ';
const int mod = 666013;
const int inf = 0x3f3f3f3f;
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int N = 12e4;
struct point {
long double x, y;
} v[N + 1];
int n;
bool trigorder(const point& a, const point& b, const 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) {
return trigorder(v[1], a, b);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
fin >> n;
int foo = 1;
for (int i = 1; i <= n; ++i) {
fin >> v[i].x >> v[i].y;
if (v[foo].x > v[i].x || (v[foo].x == v[i].x && v[foo].y > v[i].y)) {
foo = i;
}
}
swap(v[foo], v[1]);
// v[1] - punctul de la care incepem
sort(v + 2, v + n + 1, cmp);
vector<int> H{ 1, 2 };
for (int i = 3; i <= n; ++i) {
while (!trigorder(v[H[H.size() - 2]], v[H.back()], v[i])) {
H.pop_back();
}
H.push_back(i);
}
fout << H.size() << nl;
for (auto& i : H) {
fout << fixed << setprecision(6) << v[i].x << sp << v[i].y << nl;
}
}