Pagini recente » Cod sursa (job #1009007) | Mihnea Andreescu | Monitorul de evaluare | Istoria paginii runda/training_day_5/clasament | Cod sursa (job #2294518)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define NMAX 120005
#define input "infasuratoare.in"
#define output "infasuratoare.out"
using namespace std;
ifstream in(input);
ofstream out(output);
struct p
{
long double x, y;
} points[NMAX], stack[NMAX];
p lowest = { 1000000005, 1000000005 };
int points_size, lowest_size, stack_size;
void Swap(p &A, p &B)
{
p aux = A;
A = B;
B = aux;
}
void Read_Data()
{
in >> points_size;
for (int i = 1; i <= points_size; i++)
{
in >> points[i].x >> points[i].y;
if (points[i].x < lowest.x)
lowest = points[i], lowest_size = i;
else if (points[i].x == lowest.x)
{
if (points[i].y < lowest.y)
lowest = points[i], lowest_size = i;
}
}
Swap(points[1], points[lowest_size]);
}
double Tan_of_Angle(p A, p B, p C)
{
return (double)(B.y - A.y) * (C.x - B.x) - (C.y - B.y) * (B.x - A.x);
}
bool Sort_Method(p P1, p P2)
{
return Tan_of_Angle(points[1], P1, P2) < 0;
}
void Convex_Hull()
{
stack[1] = points[1], stack[2] = points[2], stack_size = 2;
for (int i = 3; i <= points_size; i++)
{
while (stack_size >= 2 && Tan_of_Angle(stack[stack_size - 1], stack[stack_size], points[i]) >= 0)
stack_size--;
stack[++stack_size] = points[i];
}
}
void Print_Convex_Hull()
{
out << stack_size << "\n";
for (int i = 1; i <= stack_size; i++)
out << stack[i].x << " " << stack[i].y << "\n";
}
void Control_Convex_Hull()
{
sort(points + 2, points + 1 + points_size, Sort_Method);
Convex_Hull();
Print_Convex_Hull();
}
int main()
{
out << setprecision(6) << fixed;
Read_Data();
Control_Convex_Hull();
return 0;
}