Cod sursa(job #1850904)

Utilizator TudorVersoiuVersoiu Tudor Sorin TudorVersoiu Data 19 ianuarie 2017 00:28:28
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb
#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();
}