Pagini recente » Cod sursa (job #2839731) | Cod sursa (job #1584984) | Cod sursa (job #1157091) | Cod sursa (job #1900793) | Cod sursa (job #2262666)
// Empowersoft 2017 - Archie - Convex HULL.cpp : Defines the entry point for the console application.
//
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define input "infasuratoare.in"
#define output "infasuratoare.out"
#define NMAX 120005
using namespace std;
ifstream in(input);
ofstream out(output);
struct p
{
double x, y;
};
p points[NMAX], stiva[NMAX], reper_point = { 1000000001, 1000000001 };
int puncte, reper_value, nivel;
double Check_Position_Points(p p1, p p2, p p3)
{
double distance = (double)(p2.y - p1.y)*(p3.x - p2.x) - (double)(p3.y - p2.y)*(p2.x - p1.x);
return distance;
}
void Swap_Points(p &a, p &b)
{
p aux = a;
a = b;
b = aux;
}
bool Sort_Criterium(p a, p b)
{
return Check_Position_Points(reper_point, a, b) < 0;
}
double Max(double a, double b)
{
return a > b ? a : b;
}
void Read_Data()
{
in >> puncte;
for (int i = 1; i <= puncte; i++)
{
in >> points[i].x >> points[i].y;
if (points[i].x < reper_point.x)
reper_point = points[i], reper_value = i;
else if (points[i].x == reper_point.x)
if (points[i].y < reper_point.y)
reper_point = points[i], reper_value = i;
}
Swap_Points(points[reper_value], points[1]);
sort(points + 2, points + 1 + puncte, Sort_Criterium);
}
void Convex_HULL()
{
stiva[1] = points[1];
stiva[2] = points[2];
nivel = 2;
for (int i = 3; i <= puncte; i++)
{
while (nivel >= 2 && Check_Position_Points(stiva[nivel-1], stiva[nivel], stiva[i]) >= 0)
nivel--;
stiva[++nivel] = points[i];
}
}
void Solve_Task()
{
out << nivel << "\n";
for (int i = 1; i <= nivel; i++)
out << stiva[i].x << " " << stiva[i].y << "\n";
}
int main()
{
out << setprecision(8) << fixed;
Read_Data();
Convex_HULL();
Solve_Task();
return 0;
}