Pagini recente » Cod sursa (job #2731768) | Cod sursa (job #1326337) | Cod sursa (job #2233772) | Cod sursa (job #712374) | Cod sursa (job #370619)
Cod sursa(job #370619)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on November 28, 2009, 7:59 PM
*/
#include <cmath>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstdlib>
#define pr pair< double, double>
#define pb push_back
#define mk make_pair< double, double >
/*
*
*/
using namespace std;
pr start, next, now;
vector< pr > v, convex_hull;
int main()
{bool *use;
int n, i, p;
double x, y, m, m2, last;
freopen("infasuratoare.in", "rt", stdin );
scanf("%d %lf %lf",&n, &x, &y );
use=(bool*)calloc( n, sizeof(bool) );
start=mk( x, y );
v.pb( start );
n-=1;
while( n-- )
{
scanf("%lf %lf", &x, &y );
now=mk( x, y );
if( y < start.second || ( y == start.second && x < start.first ) )
start=now;
v.pb( now );
}
n=v.size();
last=0;
convex_hull.pb( start );
while( true )
{next=start;
now=convex_hull.back();
m=1000001;
for( i=0; i < n; ++i )
if( !use[i] && now != v[i] )
{
m2=atan2( v[i].second-now.second, v[i].first-now.first );
if( m2 < 0 )
m2+=2*M_PI;
//m2-=last;
//if( m2 < 0 )
// m2+=2*M_PI;
if( m2 > last && m2 < m )
m=m2, next=v[i], p=i;
}
if( next == start )
break;
convex_hull.pb( next );
use[p]=true;
last=m;/*
last=atan2( v[p].second-now.second, v[p].first-now.first );
if( last < 0 )
last+=2*M_PI; */
}
free(use);
n=convex_hull.size();
freopen( "infasuratoare.out", "wt", stdout );
printf( "%d\n", n );
for( i=0; i < n; ++i )
printf( "%lf %lf\n", convex_hull[i].first, convex_hull[i].second );
return 0;
}