Pagini recente » Cod sursa (job #1089373) | Cod sursa (job #1360858) | Cod sursa (job #3155753) | Cod sursa (job #2757245) | Cod sursa (job #1850888)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <stack>
#define x first
#define y second
#define MAXN 120005
using namespace std;
ifstream fin ("infasuratoare.in" );
ofstream fout("infasuratoare.out");
using Point = pair<double, double>;
int nPuncte;
int stiva[MAXN], stackSize;
Point puncte[MAXN];
double panta[MAXN];
bool viz[MAXN];
//////////////////////////////////////////
void PrintPoints()
{
for ( int i=1; i<=nPuncte; i++ )
cout << puncte[i].x << ' ' << puncte[i].y << '\n';
cout << '\n';
}
void PrintSlopes()
{
for ( int i=1; i<=nPuncte; i++ )
cout << panta[i] << '\n';
cout << '\n';
}
void PrintCombined()
{
for ( int i=1; i<=nPuncte; i++ )
cout << puncte[i].x << ' ' << puncte[i].y << ' ' << panta[i] << '\n';
cout << '\n';
}
/////////////////////////////////////////////////////////////////////////////
void ReadInput()
{
fin >> nPuncte;
int best = 1;
for ( int i=1; i<=nPuncte; i++ )
{
fin >> puncte[i].x >> puncte[i].y;
if ( puncte[i].x < puncte[best].x ) { // Find the leftmost point
best = i;
} else {
if ( puncte[i].x == puncte[best].x )
if ( puncte[i].y > puncte[best].y ) // If there are multiple minimal x's choose the biggest y
best = i;
}
}
swap(puncte[1], puncte[best]); // Put x on position 1
}
double Slope(Point A, Point B) {
float height = B.y-A.y;
float dist = B.x-A.x;
dist = dist==0?1.f/1000.f:dist;
// Make sure we don't raise SIGFPE and keep elements in a column in order
return height/dist;
}
double CrossProduct(Point p1, Point p2, Point p3) {
return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}
void ConvexHull()
{
for ( int i=2; i<=nPuncte; i++ )
panta[i] = Slope(puncte[1], puncte[i]);
// Compute slope for every 1-i pair
for ( int i=2; i<=nPuncte; i++ )
for ( int j=i+1; j<=nPuncte; j++ )
if ( panta[i] > panta[j] )
{
swap(panta [i], panta [j]);
swap(puncte[i], puncte[j]);
} // Sort all points based on slope
stiva[++stackSize] = 1; viz[1] = true;
stiva[0] = nPuncte; // Make sure we dont use null value to calculate angle
for ( int i = 2; i <= nPuncte; i++ )
{
while ( stackSize > 1 && CrossProduct(puncte[stiva[stackSize-1]], puncte[stiva[stackSize]], puncte[i]) < 0 )
--stackSize;
stiva[++stackSize] = i;
}
}
void WriteStack()
{
fout << stackSize << '\n';
fout << fixed << setprecision(6);
for ( int i=1; i<=stackSize; i++ )
fout << puncte[stiva[i]].x << ' ' << puncte[stiva[i]].y << '\n';
}
int main() {
ReadInput();
ConvexHull();
WriteStack();
}