Pagini recente » Cod sursa (job #616315) | Cod sursa (job #1411633) | Cod sursa (job #2237934) | Cod sursa (job #756450) | Cod sursa (job #390906)
Cod sursa(job #390906)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on February 4, 2010, 7:16 PM
*/
#include <vector>
#include <utility>
#include <fstream>
#include <cstdlib>
#include <algorithm>
/*
*
*/
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.second-p0.second)*(p2.first-p0.first), y=(p2.second-p0.second)*(p1.first-p0.first);
if( x == y )
return p1 < p2;
return x < y;
}
inline bool check( pr p0, pr p1, pr p2 )
{
return (p2.first-p0.first)*(p1.second-p0.second) > (p1.first-p0.first)*(p2.second-p0.second);
}
int main(int argc, char** argv)
{
int n, i, j=0;
ifstream in("infasuratoare.in");
in>>n>>p0.first>>p0.second;
v.push_back(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.push_back(p);
}
swap( v[0], v[j] );
sort( v.begin()+1, v.end(), cmp );
s.push_back(v[0]);
s.push_back(v[1]);
s.push_back(v[2]);
for( i=3; i < n; ++i )
{
for( j=s.size()-1; j >= 2 && check( s[j-1], s[j], v[i] ); --j, s.pop_back() );
s.push_back(v[i]);
}
ofstream out("infasuratoare.out");
out<<s.size()<<'\n';
for( i=0, n=s.size(); i < n; ++i )
out<<s[i].first<<' '<<s[i].second<<'\n';
return (EXIT_SUCCESS);
}