Pagini recente » Cod sursa (job #2033767) | Cod sursa (job #1688034) | Cod sursa (job #712466) | Cod sursa (job #1010493) | Cod sursa (job #2039853)
#include <fstream>
#include <vector>
#include <iomanip>
#include <stack>
#include <algorithm>
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);
}
Point current_point;
bool Compare(Point& a, Point& b)
{
return Direction(current_point, a, b) == CCW;
}
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]);
}
void Graham()
{
int min_x = 0;
for (int i = 1; i < N; i++)
{
if (v[i].x < v[min_x].x)
min_x = i;
}
current_point = v[min_x];
swap(v[0], v[min_x]);
sort(v + 1, v + N, Compare);
hull[k++] = 0;
hull[k++] = 1;
for (int i = 2; i < N; i++)
{
int top = hull[k - 1];
int prev = hull[k - 2];
Dir o = Direction(v[prev], v[top], v[i]);
while (o == CW || (o == CL && Dist(v[prev], v[top]) < Dist(v[prev], v[i])))
{
k--;
int top = hull[k - 1];
int prev = hull[k - 2];
o = Direction(v[prev], v[top], v[i]);
}
hull[k++] = i;
}
}
int main()
{
in >> N;
for (int i = 0; i < N; i++)
{
in >> v[i].x >> v[i].y;
}
Graham();
out << k << '\n';
for (int i = 0; i < k; i++)
{
out << fixed << setprecision(8) << v[hull[i]].x << ' ' << v[hull[i]].y << '\n';
}
}