Pagini recente » Cod sursa (job #2817059) | Cod sursa (job #465724) | Cod sursa (job #2500376) | Cod sursa (job #3175) | Cod sursa (job #2664840)
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#define ld double
#define pd std::pair<ld, ld>
#define x first
#define y second
const int nmax = 12e4 + 5;
const ld eps = 1e-12;
std::vector<int>hull = { 0, 1 };
bool f[nmax];
bool cross(pd a, pd b, pd c) {
return (c.y * (b.x - a.x) - c.x * (b.y - a.y) + b.y * a.x - b.x * a.y < eps);
}
int main() {
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
int n, dir = 1;
fin >> n;
std::vector<pd>v(n);
for (int i = 0; i < n; i++) fin >> v[i].y >> v[i].x;
std::sort(v.begin(), v.end());
f[1] = 1;
for (int i = 2; i!=-1; i += dir)
if(!f[i]){
while (hull.size() > 1 and !cross(v[hull[hull.size() - 2]], v[hull.back()], v[i]))
f[hull.back()] = 0, hull.pop_back();
hull.push_back(i), f[hull.back()] = 1;
if (hull.back() == n - 1) dir = -1;
}
hull.pop_back();
fout << hull.size() << "\n";
for (int z:hull) fout << std::fixed << std::setprecision(12) << v[z].y << " " << v[z].x << "\n";
}