Cod sursa(job #1456384)

Utilizator petru.cehanCehan Petru petru.cehan Data 30 iunie 2015 14:46:20
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <vector>

using namespace std;

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

struct punct { double x ; double y ; } ;

vector <punct> * pct = new vector <punct> () ;

int N ;

void Citire()
{
    double  a , b ;
    int copie ;
    fin >> N ; copie = N ;
    punct * aux = new punct ;
    while ( copie >= 1 )
    {
        fin >> a >> b ;
        aux->x = a , aux->y = b ;
        pct->push_back (*aux) ;
        -- copie ;
    }
   delete aux ;
}

double CalculUnghi ( punct A , punct B )
{
    double unghi , y , x ;

    unghi = atan ( ( ( y = B.y - A.y )) / ( ( x = B.x - A.x ) ) ) ;

    if ( x > 0 )
       return unghi ;

    if ( x < 0 && y >= 0 )
       return ( unghi + 3.14 ) ;

    if ( x < 0 && y < 0 )
       return ( unghi - 3.14 ) ;

    if ( x == 0 && y > 0 )
       return 1.57 ;

    if ( x == 0 && y < 0 )
       return -1.57 ;
}

double CCW ( punct A , punct B , punct C )
{
    double d1 ;
    d1 = A.x * B.y ;
    d1 += B.x * C.y ;
    d1 += C.x * A.y ;
    d1 -= C.x * B.y ;
    d1 -= A.x * C.y ;
    d1 -= B.x * A.y ;
    return d1 ;
}

void PolarSorted ( vector <punct> * p )
{
    int i , j , poz ;
    int N = p->size() ;
    punct * min = new punct ;
    min->y = 1000000001 ;

    for ( i = 0 ; i < N ; ++ i )
        if ( p->at(i).y < min->y )
            {
              *min = p->at(i) ; poz = i ;
            }
    delete min ;

    punct * aux = new punct ;
    *aux = p->at (poz) ;
    p->at (poz) = p->at (0) ;
    p->at (0) = *aux ;

    for ( i = 1 ; i < N - 1 ; ++ i )
      for ( j = i + 1 ; j < N ; ++ j )
              if ( CalculUnghi ( p->at (0) , p->at (i) ) >= CalculUnghi ( p->at (0) , p->at(j) ) )
                          *aux = p->at (j) , p->at (j) = p->at (i) , p->at (i) = *aux ;

    delete aux ;
}

void ConvexHull ( vector <punct> * p )
{
     PolarSorted (p) ;
     unsigned int i ;
     for ( i = 2 ; i < p->size() ; ++ i )
         if ( CCW ( p->at (i-2), p->at (i-1) , p->at (i)) < 0 )
                       p->erase ( p->begin() + ( -- i ) ) ;
}

int main()
{
    Citire () ;
    ConvexHull ( pct ) ;
    unsigned int i ;

    fout << pct->size () << "\n" ;

    for ( i = 0 ; i < pct->size () ; ++ i )
          fout << fixed << setprecision(10)<< pct ->at (i).x << " " << pct->at (i).y << "\n" ;

    return 0;
}