Pagini recente » Cod sursa (job #1181311) | Cod sursa (job #301450) | Cod sursa (job #1005003) | Cod sursa (job #827538) | Cod sursa (job #2268450)
// Teoretic Pure - Convex HULL.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define input "infasuratoare.in"
#define output "infasuratoare.out"
using namespace std;
ifstream in(input);
ofstream out(output);
struct punct
{
double x, y;
};
punct puncte[120005], convex_h[120005];
int nr_puncte, stack_level = 0;
int maximum = 0;
punct lowest_p = { 1000000000, 1000000000 };
void Read_Data()
{
in >> nr_puncte;
for (int i = 1; i <= nr_puncte; i++)
in >> puncte[i].x >> puncte[i].y;
}
inline bool Compare_Criteria(punct a, punct b)
{
if (a.x == b.x) return a.y < b.y ? 1 : 0;
return a.x < b.x ? 1 : 0;
}
inline bool Check_Identic(punct a, punct b)
{
if (a.x == b.x && a.y == b.y) return true;
return false;
}
void Swap_Points(punct &a, punct &b)
{
punct aux = a;
a = b;
b = aux;
}
double Position_of_Points(punct a, punct b, punct c)
{
// <0 - anticlockwise
// ==0 - colinear
// >0 - clockwise
double slope_AB = (double)(a.y - b.y) / (double)(a.x - b.x);
double slope_BC = (double)(b.y - c.y) / (double)(b.x - c.x);
// Difference between x coordinates can be null, so we expand the ecuation
return ((double)(b.y - a.y)*(c.x - b.x) - (c.y - b.y)*(b.x - a.x));
}
inline bool Sort_M(punct a, punct b)
{
double val = Position_of_Points(lowest_p, a, b);
return val < 0;
}
void Convex_HULL()
{
for (int i = 1; i < nr_puncte; i++)
for (int j = i + 1; j <= nr_puncte; j++)
{
punct a = puncte[i], b = puncte[j];
// Ecuatie: Ax+By+C=0
double A = 0, B = 0, C = 0;
A = b.y - a.y;
B = a.x - b.x;
C = a.y * b.x - a.x * b.y;
int to_left = 0, to_right = 0;
for (int k = 1; k <= nr_puncte; k++)
{
double val = A * puncte[k].x + B * puncte[k].y + C;
if (val < 0) to_left++;
if (val > 0) to_right++;
}
if (to_left == nr_puncte - 2 || to_right == nr_puncte - 2)
{
convex_h[++stack_level] = a, convex_h[++stack_level] = b;
}
}
sort(convex_h + 1, convex_h + 1 + stack_level, Compare_Criteria);
for (int i = 1; i < stack_level; i++)
if (Check_Identic(convex_h[i], convex_h[i + 1])) convex_h[i] = { 0, 0 };
for (int i = 1; i <= stack_level; i++)
if (convex_h[i].x != 0 || convex_h[i].y != 0)
{
int k = i;
while (k > 1 && convex_h[k - 1].x == 0 && convex_h[k - 1].y == 0)
convex_h[--k] = convex_h[k + 1], convex_h[k + 1] = { 0, 0 };
maximum = k;
}
out << maximum << "\n";
}
void Sort_Anti_ClockWise()
{
out << setprecision(6) << fixed;
int p = 0;
for (int i = 1; i <= maximum; i++)
{
if (convex_h[i].x < lowest_p.x) lowest_p = convex_h[i], p = i;
else if (convex_h[i].x == lowest_p.x)
{
if (convex_h[i].y < lowest_p.y)
lowest_p = convex_h[i], p = i;
}
}
Swap_Points(convex_h[1], convex_h[p]);
sort(convex_h + 2, convex_h + 1 + maximum, Sort_M);
for (int i = 1; i <= maximum; i++)
out << convex_h[i].x << " " << convex_h[i].y << "\n";
}
int main()
{
Read_Data();
Convex_HULL();
Sort_Anti_ClockWise();
return 0;
}