Cod sursa(job #2680967)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 4 decembrie 2020 18:32:15
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

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

struct Punct
{
    int x, y;
};

Punct P[100002], St[1002];
int N, H;

void afis()
{
    g << H << '\n';

    for ( int i = 1; i <= H; i++ )
        g << St[i].x << ' ' << St[i].y << '\n';
}

void swap ( Punct &A, Punct &B )
{
    Punct aux;
    aux = A;
    A = B;
    B = aux;
}

inline long long patrat ( long long x )
{
    return x * x;
}

long long distp ( const Punct &A, const Punct &B )
{
    return patrat ( A.x - B.x ) + patrat ( A.y - B.y );
}

int compy ( const Punct &A, const Punct &B )
{
    if ( A.y == B.y ) return A.x < B.x;

    return A.y < B.y;
}

long long det ( const Punct &A, const Punct &B, const Punct &C )
{
    return ( long long ) ( A.x - B.x ) ( B.y - C.y ) - ( long long ) ( A.y - B.y ) ( B.x - C.x );
}

int compd ( const Punct &A, const Punct &B )
{
    long long dd = det ( P[1], A, B );

    if ( dd == 0 )
        return distp ( P[1], A ) < distp ( P[1], B );

    return dd > 0;
}

int main()
{
    f >> N;
    int pmin = 1;

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

        if ( compy ( P[i], P[pmin] ) )
            pmin = i;
    }

    swap ( P[pmin], P[1] );
    sort ( P + 2, P + N + 1, compd );
    St[1] = P[1];
    St[2] = P[2];
    H = 2;
    P[N + 1] = P[1];

    for ( int i = 3; i <= N + 1; i++ )
    {
        while ( H >= 2 && det ( St[H - 1], St[H], P[i] ) <= 0 )
            H--;

        St[++H] = P[i];
    }

    H--;
    afis();
    return 0;
}