Pagini recente » Cod sursa (job #1223074) | Cod sursa (job #1741866) | Cod sursa (job #1216820) | Cod sursa (job #247170) | Cod sursa (job #390939)
Cod sursa(job #390939)
/*
* 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);
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.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(), 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;
}