Cod sursa(job #1850888)

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