Pagini recente » Cod sursa (job #2067488) | Cod sursa (job #394784) | Cod sursa (job #918843) | Cod sursa (job #1545189) | Cod sursa (job #1456547)
#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 * refe = new punct () ;
bool cmp ( punct A , punct B )
{
return ( CalculUnghi ( *refe , A ) < CalculUnghi ( *refe , 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) ;
*refe = *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 refe ;
delete pct ;
return 0;
}