Pagini recente » Autumn Warm Up 2007 | Cod sursa (job #2793389) | Cod sursa (job #1686244) | Cod sursa (job #2775978) | Cod sursa (job #2261005)
// Infasuratoare convexa - teorie.cpp : Defines the entry point for the console application.
//
#include <fstream>
#include <algorithm>
#define input "infasuratoare.in"
#define output "infasuratoare.out"
#define ARR_SIZE 120005
using namespace std;
ifstream in(input);
ofstream out(output);
struct coord
{
double x, y;
};
coord points[ARR_SIZE], stack[ARR_SIZE], first_point = {1000000000, 1000000000};
int puncte, coresp;
bool Sort_Criteria(coord f2, coord f3)
{
double value = (double)(f2.y - first_point.y)*(f3.x - f2.x) - (f3.y - f2.y)*(f2.x - first_point.x);
return value < 0;
}
double Position_of_Points(coord a, coord b, coord 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));
}
void Swap_Points(coord &p1, coord &p2)
{
coord aux = p1;
p1 = p2;
p2 = aux;
}
void Read_Data()
{
in >> puncte;
for (int i = 1; i <= puncte; i++)
{
in >> points[i].x >> points[i].y;
// Find most low point
if (points[i].x < first_point.x)
first_point = points[i], coresp = i;
else if (points[i].x == first_point.x)
if (points[i].y < first_point.y)
first_point = points[i], coresp = i;
}
swap(points[1], points[coresp]);
sort(points + 2, points + 1 + puncte, Sort_Criteria);
}
void Check_Daca_Ce_Vor_Dusmanii_S_a_Adeverit()
{
stack[1] = points[1];
stack[2] = points[2];
int nivel = 2;
for (int i = 3; i <= puncte; i++)
{
while (nivel >= 2 && Position_of_Points(stack[nivel - 1], stack[nivel], points[i]) > 0)
nivel--;
stack[++nivel] = points[i];
}
out << nivel << "\n";
for (int i = 2; i <= nivel; i++)
out << stack[i].x << " " << stack[i].y << "\n";
out << stack[1].x << " " << stack[1].y << "\n";
}
int main()
{
Read_Data();
//out << puncte << "\n";
//for (int i = 1; i <= puncte; i++)
//out << points[i].x << " " << points[i].y << "\n";
//out << "\n";
Check_Daca_Ce_Vor_Dusmanii_S_a_Adeverit();
return 0;
}