Pagini recente » Cod sursa (job #288649) | Cod sursa (job #757826) | Cod sursa (job #2222155) | Cod sursa (job #1419018) | Cod sursa (job #2416709)
#include <fstream>
#include <cstring>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAXN = 120005;
int n;
pair<double, double> v[MAXN];
double det(pair<double, double> a, pair<double, double> b, pair<double, double> c) {
return a.first * b.second + b.first * c.second + c.first * a.second - b.second * c.first - c.second * a.first - a.second * b.first;
}
bool srt(pair<double, double> a, pair<double, double> b) {
return (det(v[1], a, b) < 0);
}
int s;
pair<double, double> sol[MAXN];
int main() {
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> v[i].first >> v[i].second;
}
sort(v + 1, v + n + 1);
sort(v + 2, v + n + 1, srt);
sol[++s] = v[1];
sol[++s] = v[2];
for (int i = 3; i <= n; ++i) {
while (s > 2 && det(sol[s - 1], sol[s], v[i]) >= 0) {
s--;
}
sol[++s] = v[i];
}
fout << s << '\n';
fout << fixed << setprecision(6);
for (int i = 1; i <= s; ++i) {
fout << sol[i].first << ' ' << sol[i].second << '\n';
}
fout.close();
return 0;
}