Cod sursa(job #928464)

Utilizator matei_cChristescu Matei matei_c Data 26 martie 2013 14:21:17
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 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 rezolvare()
{
    int ind = 1 ;

    printf("%d\n", inf[1]);
    sel[ inf[1] ] = true ;

    for(int i = 2; ind == i-1 && i <= n; ++i )
    {
        if( i == 3)
        sel[inf[1]] = false;
        int last = inf[i-1];
        int next ;

        for(int j = 1; j <= n; ++j )
            if( sel[j] == false )
                {
                    next = j;
                    break;
                }

        for( int j = next + 1; j <= n; ++j)
        {
            if( j != last  )
            {
                double A = v[next].y - v[last].y ;
                double B = v[last].x - v[next].x ;
                double C = v[next].x * v[last].y - v[last].x * v[next].y ;

                double expr = A * v[j].x + B * v[j].y + C ;

                if( comp( expr, 0 ) == 1 )
                   next = j;


            }
        }
        printf("%d\n", next);
        ++ind ;
        inf[ind] = next ;
        sel[next] = true ;
        if( next == inf[1])
            break;

    }

    return ind - 1;
}

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 ;
}