Pagini recente » Cod sursa (job #1846413) | Cod sursa (job #1797671) | Cod sursa (job #1846886) | Cod sursa (job #135907) | Cod sursa (job #2878542)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define x first
#define y second
#define Point pair<double, double>
double det(Point a, Point b, Point c) { // unghiul polar
return (b.y - a.y) * (c.x - a.x) - (b.x - a.x) * (c.y - a.y);
}
int main() {
int n;
fin >> n;
vector<Point> pts(n);
for (int i = 0; i < n; i++)
fin >> pts[i].x >> pts[i].y;
swap(pts.front(), *min_element(pts.begin(), pts.end())); // functie pt determinarea minimului
sort(pts.begin() + 1, pts.end(), [&](Point a, Point b) { // sortare cu functie inline
return det(a, pts[0], b) < 0;
});
vector<Point> st; // Adaugam punctele in infasuratoare
st.push_back(pts[0]);
st.push_back(pts[1]);
for (int i = 2; i < n; i++) {
while (st.size() > 2 && det(st[st.size() - 2], st[st.size() - 1], pts[i]) < 0)
st.pop_back();
st.push_back(pts[i]);
}
fout << st.size() << fixed << setprecision(6) << '\n';
for (int i = st.size() - 1; i >= 0; i--)
fout << st[i].x << ' ' << st[i].y << '\n';
return 0;
}