Cod sursa(job #2121555)

Utilizator TudorVersoiuVersoiu Tudor Sorin TudorVersoiu Data 3 februarie 2018 20:35:02
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.74 kb
#include <iostream>
#include <fstream>
#include <limits>
#include <iomanip>


using namespace std;
ifstream f("infasuratoare.in" );
ofstream g("infasuratoare.out");

int N, refPoint;
int infas[100003];
float slope[100003];
pair<float, float> point[100003];



void ReadData()
{
    f >> N;

    for ( int i=1; i<=N; i++ )
        f >> point[i].first >> point[i].second;
}

/// Functia determinant folosita sa comparam doua unghiuri
/// Returneaza pozitiv daca C se afla in stanga dreptei AB
template<typename T>
T Determinant(pair<T, T> A, pair<T, T> B, pair<T, T> C) {
    return (A.first*B.second + B.first*C.second + C.first*A.second) - (B.second*C.first + A.second*B.first + A.first*C.second);
}

/// Functia ComputeSlope returneaza panta facuta de dreapta AB
template<typename T>
float ComputeSlope(pair<T, T> A, pair<T, T> B)
{
    float diffY = B.second - A.second;
    float diffX = B.first  - A.first;

    if ( diffX == 0 )
    {
        if ( diffY > 0 ) return numeric_limits<float>::max();
        if ( diffY < 0 ) return numeric_limits<float>::min();
        return 0;
    }

    return diffY / diffX;
}

/// Rezolvare convex hull
void ComputeConvex()
{
    int refPoint = 1;
    for ( int i=1; i<=N; i++ )
        if ( point[i].first <  point[refPoint].first ||
            (point[i].first == point[refPoint].first && point[i].second < point[refPoint].second) )
                refPoint = i;

    swap(point[refPoint], point[1]); refPoint = 1;
    /// Cautare cel mai din stanga de jos punct pe care il vom folosi ca referinta
    /// Acest punct se afla sigur pe infasuratoare

    for ( int i=2; i<=N; i++ )
        slope[i] = ComputeSlope(point[refPoint], point[i]);
    /// Calculam panta de la punctul de referinta pana la fiecare dintre celelalte

    for ( int i=2; i<N; i++ )
        for ( int j=i+1; j<=N; j++ )
            if ( slope[j] < slope[i] )
            {
                swap(slope[i], slope[j]);
                swap(point[i], point[j]);
            }
    /// Sortam pantele calculate pentru a le parcurge in ordinea in care pot aparea in infasuratoare

    infas[++infas[0]] = refPoint;
    point[N+1] = point[refPoint];

    for ( int i=2; i<=N+1; i++ )
    {
        while ( infas[0] > 1 && Determinant(point[infas[infas[0]-1]], point[i], point[infas[infas[0]]]) > 0 )
            --infas[0];
        infas[++infas[0]] = i;
    }
        /// Parcurgem toate punctele in ordinea unghiului pe care il fac cu punctului de referinta
}

int main()
{
    ReadData();
    ComputeConvex();

    g << infas[0] - 1 << '\n';

    g << fixed << setprecision(6);
    for ( int i=1; i<infas[0]; i++ )
        g << point[infas[i]].first << ' ' << point[infas[i]].second << '\n';
}