Cod sursa(job #1456397)

Utilizator petru.cehanCehan Petru petru.cehan Data 30 iunie 2015 15:44:00
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>

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

punct * ref = new punct () ;
bool cmp ( punct A , punct B )
{
    return ( CalculUnghi(*ref,A) < CalculUnghi(*ref,B) ) ;
}

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

    *ref = *min;
     delete min ;
     sort ( p->begin()+1 , p->end() , cmp );
}

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(6)<< pct ->at (i).x << " " << pct->at (i).y << "\n" ;

    delete ref ;
    delete pct ;

    return 0;
}