Pagini recente » Cod sursa (job #47479) | Cod sursa (job #2811902) | Cod sursa (job #1819538) | Cod sursa (job #1076209) | Cod sursa (job #2737192)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define mp make_pair
#define pdd pair <double, double>
using namespace std;
double det(pdd a, pdd b, pdd c) {
double res = 0;
res += a.first * b.second;
res += b.first * c.second;
res += c.first * a.second;
res -= b.second * c.first;
res -= c.second * a.first;
res -= a.second * b.first;
return res;
}
vector <pdd> ConvexHull(vector <pdd> p) {
vector <pdd> stk;
for (int i = 0; i < p.size(); ++i) {
while (stk.size() >= 2 && det(stk[stk.size() - 2], stk.back(), p[i]) < 0)
stk.pop_back();
stk.push_back(p[i]);
}
return stk;
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N;
fin >> N;
vector <pdd> points(N);
for (int i = 0; i < N; ++i) {
fin >> points[i].first >> points[i].second;
}
sort(points.begin(), points.end());
vector <pdd> underPoints, overPoints;
underPoints.push_back(points[0]);
overPoints.push_back(points[0]);
for (int i = 1; i < N - 1; ++i) {
if (det(points[0], points[i], points.back()) >= 0) {
underPoints.push_back(points[i]);
}
else {
overPoints.push_back(points[i]);
}
}
underPoints.push_back(points.back());
overPoints.push_back(points.back());
reverse(overPoints.begin(), overPoints.end());
vector <pdd> hullUnder = ConvexHull(underPoints);
vector <pdd> hullOver = ConvexHull(overPoints);
hullUnder.pop_back();
hullOver.pop_back();
vector <pdd> hull;
for (auto& i : hullUnder)
hull.push_back(i);
for (auto& i : hullOver)
hull.push_back(i);
fout << hull.size() << "\n";
fout << setprecision(12) << fixed;
for (auto& i : hull) {
fout << i.first << " " << i.second << "\n";
}
fin.close();
fout.close();
return 0;
}