Pagini recente » Cod sursa (job #2798261) | Cod sursa (job #957985) | Cod sursa (job #2869635) | Cod sursa (job #1797809) | Cod sursa (job #370461)
Cod sursa(job #370461)
/*
* 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, next, now;
vector< pr > v, convex_hull;
int main()
{int n, i, p;
double x, y, last=0, m ,m2;
bool *use;
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();
convex_hull.pb( start );
while( true )
{now=convex_hull.back(); next=start;
m=11000000001;
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 point is counterclockwise
m2+=2*M_PI;
if( m2 < m && m2 > last )
m=m2, next=v[i], p=i;
}
if( next == start )
break;
convex_hull.pb( next );
use[p]=true;
last=m;
}
out.open("infasuratoare.out");
out<<(n=convex_hull.size())<<'\n';
for( n-=1; n >= 0; --n )
out<<convex_hull[n].first<<' '<<convex_hull[n].second<<'\n';
free(use);
return 0;
}