Pagini recente » Cod sursa (job #1952640) | Cod sursa (job #1425475) | Cod sursa (job #1821566) | Cod sursa (job #1877010) | Cod sursa (job #391126)
Cod sursa(job #391126)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on February 4, 2010, 9:25 PM
*/
#include <cstdio>
#include <vector>
#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 ( (p0.first*p1.second+p1.first*p2.second+p0.second*p2.first) >= (p2.first*p1.second+p2.second*p0.first+p1.first*p0.second) );
}
int main()
{
pr p0, p;
int n, i, j=0;
freopen("infasuratoare.in", "rt", stdin );
scanf("%d%lf%lf", &n, &p0.first, &p0.second );
v.pb(p0);
for( i=1; i < n; ++i )
{
scanf("%lf%lf", &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() );
s.pb(v[0]);
s.pb(v[1]);
s.pb(v[2]);
for( i=3; i < n; ++i )
{
for( j=s.size(); j >= 2 && cmp( s[j-2], s[j-1], v[i] ); --j )
s.pp();
s.pb(v[i]);
}
freopen("infasuratoare.out", "wt", stdout );
printf("%d\n", n=s.size() );
for( ; n; --n )
printf( "%lf %lf\n", s[n-1].first, s[n-1].second );
return 0;
}