Pagini recente » Cod sursa (job #738048) | Cod sursa (job #549019) | Cod sursa (job #1496576) | Cod sursa (job #2793343) | Cod sursa (job #2039796)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
typedef pair<double, double> Point;
enum Dir{CW, CCW, CL};
double Dist(Point a, Point b)
{
double dx = a.first - b.first;
double dy = a.second - b.second;
return dx * dx + dy * dy;
}
Dir Direction(Point a, Point b, Point c)
{
Point ab({ b.first - a.first, b.second - a.second });
Point ac({ c.first - a.first, c.second - a.second });
double crossp = ab.first * ac.second - ab.second * ac.first;
if (crossp < 0)
return CW;
else if (crossp > 0)
return CCW;
else
return CL;
}
vector<int> Jarvis(vector<pair<double, double>> &v)
{
int min_x = 0;
for (int i = 1; i < v.size(); i++)
{
if (v[i].first < v[min_x].first)
min_x = i;
}
vector<int> hull;
int current = min_x;
int next = (current + 1) % v.size();
while (hull.empty() || current != hull.front())
{
hull.push_back(current);
for (int i = 0; i < v.size(); i++)
{
Dir o = Direction(v[current], v[next], v[i]);
if (o == CW || (o == CL && Dist(v[current], v[next]) < Dist(v[current], v[i])))
{
next = i;
}
}
current = next;
next = hull.front();
}
return hull;
}
int main()
{
int N;
in >> N;
vector<pair<double, double>> v(N);
for (int i = 0; i < N; i++)
{
in >> v[i].first >> v[i].second;
}
vector<int> hull = Jarvis(v);
out << hull.size() << '\n';
for (int i = 0; i < hull.size(); i++)
{
out << v[hull[i]].first << ' ' << v[hull[i]].second << '\n';
}
}