Cod sursa(job #928324)

Utilizator matei_cChristescu Matei matei_c Data 26 martie 2013 13:24:17
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.42 kb
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

#define maxn 120005
#define eps 0.000000000001
#define infinit 1000000000

struct punct
{
    double x, y ;
};

int n ;

punct v[maxn] ;

double xs = infinit, ys = infinit ;

int inf[maxn] ;

int sign ;

bool sel[maxn] ;

int comp(double a, double b)
{
    if( a - b < eps && a - b > -eps )
        return 0 ;

    if( a - b < -eps )
        return -1 ;

    return 1 ;
}

void citire()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; ++i )
    {
        scanf("%lf%lf", &v[i].x, &v[i].y);

        if( comp( v[i].x, xs ) == -1 )
        {
            xs = v[i].x ;
            ys = v[i].y ;
            inf[1] = i ;
        }

        if( comp( v[i].x, xs ) == 0 && comp( v[i].y, ys ) == -1 )
        {
            xs = v[i].x ;
            ys = v[i].y ;
            inf[1] = i ;
        }
    }
}

int semn(double A, double B, double C, int indp)
{
    double XX = v[indp].x ;
    double YX = v[indp].y ;

    double expr = A * XX + B * YX + C ;

    return comp( expr, 0 ) ;
}

bool verifica(int ind1, int ind2)
{
    bool ok = true ;



    double XA = v[ind1].x ;
    double YA = v[ind1].y ;

    double XB = v[ind2].x ;
    double YB = v[ind2].y ;

    double A = YB - YA ;
    double B = XA - XB ;
    double C = XB * YA - XA * YB ;


    for(int i = 1; i <= n; ++i )
    {
        if( i == ind1 || i == ind2)
            continue;
        if( semn( A, B, C, i ) > 0 )
        {
            ok = false ;
            break ;
        }
    }

    return ok ;
}

int rezolvare()
{
    bool ok = true ;

    int ind = 1 ;

    sel[ inf[1] ] = true ;

    while( ok )
    {
        ok = false ;

        for(int i = 1; i <= n; ++i )
        {
            if( sel[i] == false && verifica( inf[ind], i ) == true )
            {
                ++ind ;
                inf[ind] = i ;
                sel[i] = true ;
                ok = true ;
                break ;
            }
        }
    }
    return ind;
}

void afisare(int ind)
{
    printf("%d\n", ind);

    for(int i = 1; i <= ind; ++i )
        printf("%.6lf %.6lf\n", v[ inf[i] ].x, v[ inf[i] ].y );
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    citire() ;

    afisare(rezolvare() ) ;

    return 0 ;
}