Pagini recente » Cod sursa (job #2861071) | Cod sursa (job #1572520) | Cod sursa (job #2321253) | Cod sursa (job #2606474) | Cod sursa (job #371339)
Cod sursa(job #371339)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on December 3, 2009, 3:11 PM
*/
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#define pb push_back
#define pr pair< double, double >
#define mk make_pair< double, double >
/*
*
*/
using namespace std;
pr start, next, now;
vector< pr > v, s;
inline bool cmp( pr p1, pr p2 )
{
return (p1.first-start.first)*(p2.second-start.second) < (p2.first-start.first)*(p1.second-start.second);
}
inline bool surface( pr p0, pr p1, pr p2 )
{
double x0=p0.first, y0=p0.second;
double x1=p1.first, y1=p1.second;
double x2=p2.first, y2=p2.second;
return (x0*y1-x2*y1+x1*y2-y2*x0+y0*x2-x1*y0) >= 0 ;
}
int main()
{unsigned int n, i, j, p=0;
freopen( "infasuratoare.in", "rt", stdin );
scanf( "%u%lf%lf", &n, &now.first, &now.second );
start=now;
v.pb(now);
for( i=1; i < n; ++i )
{
scanf( "%lf%lf", &now.first, &now.second );
if( now < start )
start=now, p=i;
v.pb( now );
}
v.erase( v.begin()+p );
sort( v.begin(), v.end(), cmp );
s.pb( start );
s.pb( v[0] );
s.pb( v[1] );
for( i=2, n-=1; i < n; ++i )
{
for( j=s.size(); j >= 2 && surface( s[j-2], s[j-1], v[i] ) ; --j )
s.pop_back();
s.pb( v[i] );
}
freopen("infasuratoare.out", "wt", stdout );
printf( "%u\n", (n=s.size()) );
for( ; n; --n )
printf( "%lf %lf\n", s[n-1].first, s[n-1].second );
return 0;
}