Cod sursa(job #3203006)

Utilizator octavi26octavian octavi26 Data 12 februarie 2024 21:01:58
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <bits/stdc++.h>
#define N 120008

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int n, k;
struct point{
    double x, y;

    bool operator!=(point A){
        return A.x != x || A.y != y;
    }
    bool operator==(point A){
        return A.x == x && A.y == y;
    }
} v[N], sol[N];

void Citire()
{
    int i;
    fin >> n;
    for( i=1; i<=n; i++ ){
        fin >> v[i].x >> v[i].y;
    }
}

int Orientare( point A, point B, point C )
{
    if( (C.y - A.y)*(B.x - A.x) - (B.y - A.y)*(C.x - A.x) < 0 )
        return -1;
    if( (C.y - A.y)*(B.x - A.x) - (B.y - A.y)*(C.x - A.x) > 0 )
        return 1;
    return 0;
}

double dist( point A, point B ){
    return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}

void Rezolvare()
{
    int i;
    point P, P0;
    double xmn = 2e9;
    for( i=1; i<=n; i++ ){
        if( v[i].x < xmn ){
            xmn = v[i].x;
            P = v[i];
        }
        else if( v[i].x < xmn ) if( v[i].y < P.y ){
            P = v[i];
        }
    }
    P0 = P;

    while(true){
        sol[++k] = P;
        point NEXT;
        for( i=1; i<=n; i++ )
            if( v[i] != P ) {NEXT = v[i]; break;}

        for( i=1; i<=n; i++ )
            if( v[i] != P && v[i] != NEXT ){
                if( Orientare( P, NEXT, v[i] ) < 0 )
                    NEXT = v[i];
                else if( Orientare( P, NEXT, v[i] ) == 0 )
                    if( dist( P, v[i] ) > dist( P, NEXT ) )
                    NEXT = v[i];
            }

        if( NEXT == P0 ) break;
        P = NEXT;
    }

    fout << k << "\n";
    fout << fixed << setprecision(12);
    for( i=1; i<=k; i++ )
        fout << sol[i].x << " " << sol[i].y << "\n";
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}