Pagini recente » Cod sursa (job #2359804) | Cod sursa (job #2289928) | Cod sursa (job #2346376) | Cod sursa (job #1630726) | Cod sursa (job #1584148)
/* 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.first) * (p1.second - p3.second) -
(p1.second - p2.second) * (p1.first - p3.first);
}
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]);
while (list2.size() >= 2 && getDet3(list2[list2.size() - 2], list2.back(), points[N - 1 - i]) <= 0)
list2.pop_back();
list2.push_back(points[N - 1 - 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;
}