Pagini recente » Cod sursa (job #2377938) | Cod sursa (job #146619) | Cod sursa (job #94142) | Cod sursa (job #2505569) | Cod sursa (job #1584002)
/* Graham's Scan (Andrew's version) */
#include <fstream>
#include <cmath>
#include <vector>
#include <utility>
#include <ctime>
#include <iomanip>
#include <algorithm>
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;
double x, y;
vector<pair<double, double>> points;
for (i = 0; i < N; i++)
{
f >> x >> y;
points.push_back(make_pair(x, y));
}
f.close();
sort(points.begin(), points.end(), [] (const pair<double, double> &a, const pair<double, double> &b) -> bool
{
if (a.first == b.first)
return a.second < b.second;
return a.first < b.first;
});
vector<pair<double, double>> list1, list2;
list1.push_back(points[0]);
list1.push_back(points[1]);
list2.push_back(points.back());
list2.push_back(points[points.size() - 2]);
for (i = 2; i < N; i++)
{
while (list1.size() >= 2 && getDet3(list1[list1.size() - 2], list1.back(), points[i]) <= 0)
list1.pop_back();
list1.push_back(points[i]);
}
for (i = N - 3; i >= 0; i--)
{
while (list2.size() >= 2 && getDet3(list2[list2.size() - 2], list2.back(), points[i]) <= 0)
list2.pop_back();
list2.push_back(points[i]);
}
ofstream g("infasuratoare.out");
g << fixed << setprecision(12) << list1.size() + ((int)list2.size() - 2) << '\n';
for (i = 0; i < list1.size(); i++)
g << list1[i].first << ' ' << list1[i].second << '\n';
for (i = 1; i < list2.size() - 1; i++)
g << list2[i].first << ' ' << list2[i].second << '\n';
g.close();
return 0;
}