Pagini recente » Cod sursa (job #1249985) | Cod sursa (job #739931) | Cod sursa (job #544072) | Cod sursa (job #1259613) | Cod sursa (job #1581663)
/* Jarvis' march */
#include <fstream>
#include <cmath>
#include <vector>
#include <utility>
#include <ctime>
#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()
{
srand(time(NULL));
int N, i;
ifstream f("infasuratoare.in");
f >> N;
double x, y;
vector<pair<double, double>> points;
int extremeIndex = 0;
for (i = 0; i < N; i++)
{
f >> x >> y;
points.push_back(make_pair(x, y));
if (points[i].second < points[extremeIndex].second)
extremeIndex = i;
else if (points[i].second == points[extremeIndex].second && points[i].first < points[extremeIndex].first)
extremeIndex = i;
}
f.close();
vector<pair<double, double>> sol;
bool valid = true;
sol.push_back(points[extremeIndex]);
int pivot;
while (valid)
{
do
{
pivot = rand() % points.size();
} while (pivot == extremeIndex);
for (i = 0; i < points.size(); i++)
if (getDet3(points[extremeIndex], points[pivot], points[i]) < 0)
pivot = i;
if (points[pivot] != sol[0])
{
sol.push_back(points[pivot]);
extremeIndex = pivot;
}
else
valid = false;
}
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;
}