Pagini recente » Cod sursa (job #2102650) | Cod sursa (job #759736) | Cod sursa (job #1826035) | Cod sursa (job #2328581) | Cod sursa (job #2875289)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
class point {
public:
long double x, y;
long double operator*(point a) {
return x * a.y - y * a.x;
}
point operator-(point a) {
return { x - a.x, y - a.y };
}
};
point v[120002];
bool cmp(point a, point b) {
return ((a-v[0]) * (b-v[0]) < 0);
}
int n;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> v[i].x >> v[i].y;
}
sort(v + 1, v + n, cmp);
stack<pair<point, point>> st;
st.push({ v[0], v[1] });
for (int i = 2; i < n; i++) {
int ok = 0;
while (ok == 0) {
if (st.empty() == 1) {
ok = 1;
st.push({ st.top().second , v[i] });
break;
}
point i1 = st.top().second - st.top().first;
point i2 = v[i] - st.top().first;
if (i1 * i2 > 0) {
st.pop();
}
else {
ok = 1;
st.push({ st.top().second, v[i] });
}
}
}
vector<point>ans;
int cnt = 1;
while (st.empty() != 1) {
if (cnt == 1) {
ans.push_back(st.top().second);
cnt++;
}
ans.emplace_back(st.top().first);
st.pop();
}
cout << ans.size() << '\n';
cout << setprecision(9) << fixed;
for (int i = 0; i < ans.size(); i++) {
cout << ans[i].x << ' ' << ans[i].y << '\n';
}
}