Pagini recente » Cod sursa (job #730606) | Cod sursa (job #2510516) | Cod sursa (job #2457062) | Cod sursa (job #2766785) | Cod sursa (job #1456384)
#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;
}