Pagini recente » Cod sursa (job #2715006) | Cod sursa (job #2402462) | Cod sursa (job #1843098) | Cod sursa (job #610610) | Cod sursa (job #1850904)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <stack>
#define x first
#define y second
#define MAXN 120005
#define INPUT_FILE "infasuratoare.in"
#define OUTPUT_FILE "infasuratoare.out"
using namespace std;
ifstream fin (INPUT_FILE );
ofstream fout(OUTPUT_FILE);
using Point = pair<double, double>;
int nPuncte;
int stiva[MAXN], stackSize;
Point puncte[MAXN];
double panta[MAXN];
bool viz[MAXN];
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);
}
bool ComparePoints(Point A, Point B) {
return Slope(puncte[1], A) < Slope(puncte[1], B);
}
void ConvexHull()
{
sort(puncte+2, puncte+nPuncte+1, ComparePoints);
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(4);
for ( int i=1; i<=stackSize; i++ )
fout << puncte[stiva[i]].x << ' ' << puncte[stiva[i]].y << '\n';
}
int main() {
ReadInput();
ConvexHull();
WriteStack();
}