Pagini recente » Cod sursa (job #1169030) | Cod sursa (job #2390836) | Cod sursa (job #2732063) | Cod sursa (job #1685306) | Cod sursa (job #1581620)
/* Graham's scan */
#include <fstream>
#include <cmath>
#include <vector>
#include <utility>
#include <algorithm>
#include <iomanip>
using namespace std;
double getDet3(const pair<double, double> &p1,
const pair<double, double> &p2,
const pair<double, double> &p3)
{
return p1.first * (p2.second - p3.second) +
p2.first * (p3.second - p1.second) +
p3.first * (p1.second - p2.second);
}
int main()
{
int N, i;
ifstream f("infasuratoare.in");
f >> N;
pair<double, double> points[N];
int centerIndex = 0;
for (i = 0; i < N; i++)
{
f >> points[i].first >> points[i].second;
if (points[i].second < points[centerIndex].second)
centerIndex = i;
else if (points[i].second == points[centerIndex].second && points[i].first < points[centerIndex].first)
centerIndex = i;
}
f.close();
swap(points[0], points[centerIndex]);
centerIndex = 0;
sort(points + 1, points + N, [&] (const pair<double, double> &a, const pair<double, double> &b) {
return getDet3(points[centerIndex], a, b) > 0;
});
vector<pair<double, double>> sol;
sol.push_back(points[0]);
sol.push_back(points[1]);
for (i = 2; i < N; i++)
{
while (sol.size() > 2 && getDet3(sol[sol.size() - 2], sol.back(), points[i]) <= 0)
sol.pop_back();
sol.push_back(points[i]);
}
ofstream g("infasuratoare.out");
g << fixed << setprecision(12) << sol.size() << '\n';
for (auto it = sol.begin(); it != sol.end(); it++)
g << it->first << ' ' << it->second << '\n';
g.close();
return 0;
}