Pagini recente » Cod sursa (job #1676525) | Cod sursa (job #597961) | Cod sursa (job #1796696) | Cod sursa (job #1031692) | Cod sursa (job #367951)
Cod sursa(job #367951)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on November 22, 2009, 3:40 PM
*/
#include <cmath>
#include <vector>
#include <utility>
#include <fstream>
#define pb push_back
#define mk make_pair< double, double >
/*
*
*/
using namespace std;
ifstream in;
ofstream out;
vector< pair< double, double > > v, convex_hull;
vector< pair< double, double > >::iterator it, iend, start, next, now;
int main()
{int n;
double x, y, maxim, maxim2;
in.open("infasuratoare.in");
in>>n;
while( n-- )
{
in>>x>>y;
v.pb( mk( x, y ) );
}
for( start=v.begin(), it=start+1, iend=v.end(); it < iend; ++it )
if( it->first < start->first )
start=it;
else if( it->first == start->first && it->second < start->second )
start=it;
convex_hull.pb( *start );
while( !v.empty() )
{now=convex_hull.begin()-1; next=v.begin();
maxim=atan2( next->first - now->first, next->second - now->second )+2*M_PI;
for( it=next+1, iend=v.end(); it < iend; ++it )
{
maxim2=atan2( it->first - now->first, it->second - now->second )+2*M_PI;
if( maxim2 > maxim )
next=it, maxim=maxim2;
}
if( start->first == next->first && start->second == next->second )
break;
convex_hull.pb( *next );
v.erase( next );
}
out.open("infasuratoare.out");
n=convex_hull.size();
out<<n<<'\n';
for( n-=1; n >= 0; --n )
out<<convex_hull[n].first<<' '<<convex_hull[n].second<<'\n';
return 0;
}