Pagini recente » Cod sursa (job #1664281) | Cod sursa (job #1104663) | Cod sursa (job #2890559) | Cod sursa (job #1041360) | Cod sursa (job #3268213)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct Info {
double x;
double y;
int idx;
Info() = default;
Info(double x, double y) : x(x), y(y) {}
};
int n;
vector<Info> v;
void read() {
cin >> n;
v.resize(n + 1);
for (int i = 1; i <= n; i++) {
cin >> v[i].x >> v[i].y;
v[i].idx = i;
}
}
bool orientation(const Info &a1, const Info &a2, const Info &a3) {
vector<vector<double>> mat(3, vector<double>(3));
mat[0][0] = a1.x;
mat[1][0] = a1.y;
mat[2][0] = 1;
mat[0][1] = a2.x;
mat[1][1] = a2.y;
mat[2][1] = 1;
mat[0][2] = a3.x;
mat[1][2] = a3.y;
mat[2][2] = 1;
return (mat[0][0] * mat[1][1] * mat[2][2] + mat[1][0] * mat[2][1] * mat[0][2] + mat[2][0] * mat[0][1] * mat[1][2]
- mat[0][2] * mat[1][1] * mat[2][0] - mat[1][2] * mat[2][1] * mat[0][0] - mat[2][2] * mat[0][1] * mat[1][0])
> 0;
}
void solve() {
sort(v.begin() + 1, v.end(), [](const Info &a1, const Info &a2) -> bool {
if (a1.y == a2.y) {
return a1.x < a2.x;
}
return a1.y < a2.y;
});
Info pivot = v[1];
sort(v.begin() + 2, v.end(), [&pivot](const Info &a1, const Info &a2) -> bool {
return orientation(pivot, a1, a2);
});
vector<Info> hull;
hull.emplace_back(v[1]);
hull.emplace_back(v[2]);
for (int i = 3; i < v.size(); i++) {
while (hull.size() >= 2 && orientation(hull[hull.size() - 2], hull[hull.size() - 1], v[i]) == false) {
hull.pop_back();
}
hull.emplace_back(v[i]);
}
cout << hull.size() << "\n";
for (auto it : hull) {
cout << fixed << setprecision(10) << it.x << " " << it.y << "\n";
}
}
int main() {
read();
solve();
return 0;
}