Pagini recente » Cod sursa (job #208439) | Cod sursa (job #716627) | Cod sursa (job #1878174) | Cod sursa (job #1585430) | Cod sursa (job #370543)
Cod sursa(job #370543)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on November 28, 2009, 7:59 PM
*/
#include <cmath>
#include <vector>
#include <utility>
#include <fstream>
#include <cstdlib>
#define pb push_back
#define mk make_pair< double, double >
#define pr pair< double, double >
/*
*
*/
using namespace std;
ifstream in;
ofstream out;
pr start, now, next;
vector< pr > v, convex_hull;
int main()
{bool *use;
int n, i, p=0;
double x, y, m, m2, last;
in.open("infasuratoare.in");
in>>n>>x>>y;
use=(bool*)calloc( n, sizeof(bool) );
start=mk( x, y );
v.pb( start );
n-=1;
while( n-- )
{
in>>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 ) //if it's counterclokwise
m2+=2*M_PI;
m2-=last;
if( m2 < 0 )
m2+=2*M_PI;
if( m2 < m )
m=m2, next=v[i], p=i;
}
if( next == start )
break;
convex_hull.pb( next );
use[p]=true;
last=m;
}
free(use);
n=convex_hull.size();
out.open("infasuratoare.out");
out<<n<<'\n';
for( i=0; i < n; ++i )
out<<convex_hull[i].first<<' '<<convex_hull[i].second<<'\n';
return 0;
}