Pagini recente » Cod sursa (job #68951) | Cod sursa (job #2875323) | Cod sursa (job #67678) | Cod sursa (job #1706613) | Cod sursa (job #2873085)
#include <bits/stdc++.h>
using namespace std;
typedef pair<double, double> pd;
bool shouldPop(pd a, pd b, pd c) {
double slope1 = (b.second - a.second) / (b.first - a.first);
double slope2 = (c.second - a.second) / (c.first - a.first);
return slope2 > slope1;
}
int main() {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
cin >> n;
vector<pd> points;
while (n--) {
double x, y;
cin >> x >> y;
points.emplace_back(x, y);
}
cin.close();
sort(points.begin(), points.end());
vector<pd> ans[2];
for (int cnt = 0; cnt < 2; ++cnt) {
vector<pd> st;
for (auto& i: points) {
while (st.size() > 1 && shouldPop(st.end()[-2], st.end()[-1], i))
st.pop_back();
st.push_back(i);
i.second = -i.second;
}
ans[cnt] = st;
}
reverse(ans[0].begin(), ans[0].end());
ans[0].pop_back();
ans[1].pop_back();
cout << ans[0].size() + ans[1].size() << "\n";
for (auto i: ans[0])
cout << fixed << setprecision(12) << i.first << " " << i.second << "\n";
for (auto i: ans[1])
cout << fixed << setprecision(12) << i.first << " " << -i.second << "\n";
cout.close();
return 0;
}