Pagini recente » Cod sursa (job #1284490) | Cod sursa (job #547849) | Cod sursa (job #703363) | Cod sursa (job #631760) | Cod sursa (job #2039841)
#include <fstream>
#include <vector>
#include <iomanip>
#include <stack>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct Point
{
double x, y;
};
enum Dir{CW, CCW, CL};
#define MAX 120000
Point v[MAX];
int hull[MAX];
int N, k;
double Dist(Point a, Point b)
{
double dx = a.x - b.x;
double dy = a.y - b.y;
return dx * dx + dy * dy;
}
Dir Direction(Point& a, Point& b, Point& c)
{
Point ab{ b.x - a.x, b.y - a.y };
Point ac{ c.x - a.x, c.y - a.y };
double crossp = ab.x * ac.y - ab.y * ac.x;
return (crossp < 0) ? CW : (crossp > 0 ? CCW : CL);
}
void Jarvis()
{
int min_x = 0;
for (int i = 1; i < N; i++)
{
if (v[i].x < v[min_x].x)
min_x = i;
}
k = 0;
int current = min_x;
int next;
do{
hull[k++] = current;
next = 0;
for (int i = 1; i < N; i++)
{
Dir o = Direction(v[current], v[next], v[i]);
if (current == next || o == CW ||
(o == CL && Dist(v[current], v[next]) < Dist(v[current], v[i])))
{
next = i;
}
}
current = next;
} while (current != hull[0]);
}
vector<int> Graham(vector<Point> &v)
{
return vector<int>();
}
int main()
{
in >> N;
for (int i = 0; i < N; i++)
{
in >> v[i].x >> v[i].y;
}
Jarvis();
out << k << '\n';
for (int i = 0; i < k; i++)
{
out << fixed << setprecision(8) << v[hull[i]].x << ' ' << v[hull[i]].y << '\n';
}
}