Pagini recente » Cod sursa (job #596094) | Cod sursa (job #2181595) | Cod sursa (job #2313100) | Cod sursa (job #1183761) | Cod sursa (job #2849316)
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
#define cin in
#define cout out
#endif // LOCAL
typedef double data_t;
constexpr data_t EPS = 0.8e-12;
constexpr data_t PI = 3.1415926535897932384626433832795;
pair<data_t, data_t> avg;
bool cmp(pair<data_t, data_t> a, pair<data_t, data_t> b) {
data_t angle_a = atan2(a.second - avg.second, a.first - avg.first);
if(angle_a <= 0) angle_a += 2 * PI;
data_t angle_b = atan2(b.second - avg.second, b.first - avg.first);
if(angle_b <= 0) angle_b += 2 * PI;
return angle_a <= angle_b;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<pair<data_t, data_t>> pts(n);
for(auto &e : pts) cin >> e.first >> e.second;
sort(pts.begin(), pts.end());
vector<bool> chosen(n, false);
{
// From left to right
data_t range_l = pts[0].second, range_r = pts[0].second;
chosen[0] = true;
for(int i = 1; i < n; i++) {
if(pts[i].second < range_l) {
range_l = pts[i].second;
chosen[i] = true;
}
if(pts[i].second > range_r) {
range_r = pts[i].second;
chosen[i] = true;
}
}
}
{
// From right to left
data_t range_l = pts[n - 1].second, range_r = pts[n - 1].second;
chosen[n - 1] = true;
for(int i = n - 1; i >= 0; i--) {
if(pts[i].second < range_l) {
range_l = pts[i].second;
chosen[i] = true;
}
if(pts[i].second > range_r) {
range_r = pts[i].second;
chosen[i] = true;
}
}
}
vector<pair<data_t, data_t>> hull;
for(int i = 0; i < n; i++) {
if(chosen[i]) {
hull.push_back(pts[i]);
avg.first += pts[i].first;
avg.second += pts[i].second;
}
}
avg.first /= static_cast<data_t>(hull.size());
avg.second /= static_cast<data_t>(hull.size());
sort(hull.begin(), hull.end(), cmp);
cout << hull.size() << endl;
for(auto e : hull)
cout << fixed << setprecision(10) << e.first << " " << e.second << endl;
}