Cod sursa(job #2121576)

Utilizator TudorVersoiuVersoiu Tudor Sorin TudorVersoiu Data 3 februarie 2018 21:17:44
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <limits>
#include <iomanip>

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

int N, refPoint;
int infas[100003];
double slope[100003];

struct PT {
    double x;
    double y;
    double slope;
}point[100003];
bool cmp(PT A, PT B) { return A.slope < B.slope; }

/// Functia determinant folosita sa comparam doua unghiuri
/// Returneaza pozitiv daca C se afla in stanga dreptei AB
double Determinant(PT A, PT B, PT C) {
    return (A.x*B.y + B.x*C.y + C.x*A.y) - (B.y*C.x + A.y*B.x + A.x*C.y);
}

/// Functia ComputeSlope returneaza panta facuta de dreapta AB
double ComputeSlope(PT A, PT B)
{
    double diffY = B.y - A.y;
    double diffX = B.x - A.x;

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

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

    swap(point[refPoint], point[1]); refPoint = 1;

    for ( int i=2; i<=N; i++ )
        point[i].slope = ComputeSlope(point[refPoint], point[i]);

    sort(point+2, point+N+1, cmp);
    infas[++infas[0]] = refPoint;
    point[N+1] = point[refPoint];

    for ( int i=1; i<=N; i++ )
    {
        while ( infas[0] > 1 && Determinant(point[infas[infas[0]-1]], point[i], point[infas[infas[0]]]) >= 0 )
            --infas[0];
        infas[++infas[0]] = i;
    }
}

int main()
{
    f >> N;
    for ( int i=1; i<=N; i++ )
        f >> point[i].x >> point[i].y;

    ComputeConvex();

    g << infas[0] << '\n';
    g << fixed << setprecision(12);
    for ( int i=1; i<=infas[0]; i++ )
        g << point[infas[i]].x << ' ' << point[infas[i]].y << '\n';
}