Pagini recente » Cod sursa (job #500208) | Cod sursa (job #326550) | Cod sursa (job #1966220) | Cod sursa (job #3137499) | Cod sursa (job #1581600)
/* O(N^3) algorithm */
#include <fstream>
#include <cmath>
#include <vector>
#include <utility>
#include <algorithm>
#include <iomanip>
using namespace std;
const double INF_DOUBLE = numeric_limits<double>::max();
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];
pair<double, double> center(INF_DOUBLE, INF_DOUBLE);
int pos = 1;
for (i = 0; i < N; i++)
{
f >> points[i].first >> points[i].second;
if (points[i].second < center.second)
center = points[i],pos=i;
else if (points[i].second == center.second && points[i].first < center.first)
center = points[i],pos=i;
}
f.close();
swap(points[0],points[pos]);
sort(points+1, points+ N, [&] (const pair<double, double> &a, const pair<double, double> &b) {
/*double angleA = atan2(a.second - center.second, a.first - center.first);
double angleB = atan2(b.second - center.second, b.first - center.first);
if (angleA == angleB)
{
return sqrt((a.first - center.first) * (a.first - center.first)
+ (a.second - center.second * a.second - center.second)) <
sqrt((b.first - center.first) * (b.first - center.first)
+ (b.second - center.second) * (b.second - center.second));
}
return angleA < angleB;*/
return getDet3(center, 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';
//g << points[0].first << ' ' << points[0].second << '\n';
for (auto it = sol.begin(); it != sol.end(); it++)
g << it->first << ' ' << it->second << '\n';
g.close();
return 0;
}