Pagini recente » Cod sursa (job #944315) | Cod sursa (job #693004) | Cod sursa (job #674462) | Cod sursa (job #2457975) | Cod sursa (job #2378191)
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAXN = 120005;
int n;
pair<double, double> v[MAXN];
int sol;
pair<double, double> s[MAXN];
double det(pair<double, double> x, pair<double, double> y, pair<double, double> z) {
return x.first * y.second + y.first * z.second + z.first * x.second - y.second * z.first - z.second * x.first - x.second * y.first;
}
bool srt(pair<double, double> x, pair<double, double> y) {
return det(v[1], x, y) > 0;
}
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);
s[++sol] = v[1];
s[++sol] = v[2];
for (int i = 3; i <= n; ++i) {
while (sol > 2 && det(s[sol - 1], s[sol], v[i]) <= 0) {
sol--;
}
s[++sol] = v[i];
}
fout << sol << '\n';
fout << fixed << setprecision(6);
for (int i = 1; i <= sol; ++i) {
fout << s[i].first << ' ' << s[i].second << '\n';
}
fout.close();
return 0;
}