Pagini recente » Cod sursa (job #1926660) | Cod sursa (job #1549100) | Cod sursa (job #3282269) | Cod sursa (job #1723715) | Cod sursa (job #2267850)
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair < ld, ld > pld;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
vector < pld > v;
ld crossProduct(const pld &a, const pld &b, const pld &c) {
return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}
int main() {
int n; fin >> n;
v.resize(n);
for (auto &x: v) fin >> x.first >> x.second;
int pos = 0;
for (int i = 1; i < n; ++i) {
if (v[i].first < v[pos].first) {
pos = i;
}
}
swap(v[pos], v[0]);
sort(v.begin() + 1, v.end(), [&](const pld &a, const pld &b) {
return crossProduct(v[0], a, b) < 0.0;
});
vector < pld > A, B;
A.push_back(v[0]);
A.push_back(v[1]);
for (int i = 2; i < n; ++i) {
int top = (int)A.size();
if(A.size() >= 2 && crossProduct(A[top - 2], A[top - 1], v[i]) > 0) {
// B.push_back(A[top - 1]);
A.pop_back();
--top;
}
A.push_back(v[i]);
}
fout << (int)A.size() << "\n";
for(auto x: A) {
fout << fixed << setprecision(10) << x.first << " " << x.second << "\n";
}
return 0;
}