Pagini recente » Cod sursa (job #405800) | Cod sursa (job #1363627) | Cod sursa (job #1578372) | Cod sursa (job #2193774) | Cod sursa (job #391006)
Cod sursa(job #391006)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on February 4, 2010, 9:25 PM
*/
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>
#define pp pop_back
#define pb push_back
/*
*
*/
using namespace std;
struct pr
{
double first, second;
};
vector< pr > v, s;
inline void swap( pr& a, pr& b )
{
pr aux=a;
a=b;
b=aux;
}
inline bool operator<( pr p1, pr p2 )
{
return (p1.first-v[0].first)*(p2.second-v[0].second) > (p1.second-v[0].second)*(p2.first-v[0].first);
}
inline bool cmp( pr p0, pr p1, pr p2 )
{
return ( ( (p2.first-p0.first)*(p1.second-p0.second) ) > ( (p2.second-p0.second)*(p1.first-p0.first) ) );
}
inline istream& operator>>( istream& in, pr& x )
{
in>>x.first>>x.second;
return in;
}
inline ostream& operator<<( ostream& out, pr x )
{
out<<x.first<<' '<<x.second<<'\n';
return out;
}
int main()
{
pr p, p0;
int n, i, j=0;
ifstream in("infasuratoare.in");
in>>n>>p0;
v.pb(p0);
for( i=1; i < n; ++i )
{
in>>p;
if( p.second < p0.second || (p.second == p0.second && p.first < p0.first ) )
p0=p, j=i;
v.pb(p);
}
swap( v[0], v[j] );
sort( v.begin()+1, v.end() );
s.pb(v[0]);
s.pb(v[1]);
s.pb(v[2]);
for( i=3; i < n; ++i )
{
for( j=s.size()-1; j > 2 && cmp( s[j-1], s[j], v[i] ); --j, s.pp() );
s.pb(v[i]);
}
ofstream out("infasuratoare.out");
out<<s.size()<<'\n';
copy( s.begin(), s.end(), ostream_iterator<pr>(out) );
return 0;
}