Pagini recente » Cod sursa (job #1737893) | Istoria paginii runda/faraonu/clasament | Cod sursa (job #207643) | Cod sursa (job #1900608) | Cod sursa (job #390932)
Cod sursa(job #390932)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on February 4, 2010, 7:16 PM
*/
#include <vector>
#include <utility>
#include <fstream>
#include <cstdlib>
#include <algorithm>
#define pb push_back
/*
*
*/
using namespace std;
typedef pair< double, double > pr;
pr p0, p;
vector< pr > v, s;
inline bool cmp( pr p1, pr p2 )
{
double x=(p1.first-p0.first)*(p2.second-p0.second), y=(p1.second-p0.second)*(p2.first-p0.first);
if( x == y )
return p1 < p2;
return x < y;
}
inline bool check( pr p0, pr p1, pr p2 )
{
return ( p0.first*p1.second+p1.first*p2.second+p0.second*p2.first-p1.second*p2.first-p2.second*p0.first-p1.first*p0.second ) >= 0;
}
int main()
{
int n, i, j=0;
ifstream in("infasuratoare.in");
in>>n>>p0.first>>p0.second;
v.pb(p0);
for( i=1; i < n; ++i )
{
in>>p.first>>p.second;
if( p < p0 )
p0=p, j=i;
v.pb(p);
}
swap( v[0], v[j] );
sort( v.begin()+1, v.end(), cmp );
s.pb(v[0]);
s.pb(v[1]);
s.pb(v[2]);
for( i=3; i < n; ++i )
{
for( j=s.size(); j >= 2 && check( s[j-2], s[j-1], v[i] ); --j, s.pop_back() );
s.pb(v[i]);
}
ofstream out("infasuratoare.out");
out<<(n=s.size())<<'\n';
for( ; n; --n )
out<<s[n-1].first<<' '<<s[n-1].second<<'\n';
return 0;
}