Cod sursa(job #756590)
#include <cmath>
#include <vector>
#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <iterator>
#include <algorithm>
using namespace std;
typedef pair<double, double> pr;
const double error=1e-12;
pr p0;
vector<pr> v, ConvexHull;
namespace std {
inline istream& operator>>(istream& in, pr& x) {in>>x.first>>x.second; return in;}
inline ostream& operator<<(ostream& out, const pr& x) {out<<fixed<<setprecision(12)<<x.first<<' '<<x.second; return out;}
inline pr operator-(const pr& x, const pr& y) {pr z(x.first-y.first, x.second-y.second); return z;}
};
inline double crossProduct(const pr& x, const pr& y) {return x.first*y.second - x.second*y.first;}
inline bool cmp(const pr& x, const pr& y) {return crossProduct(x-p0, y-p0) < error;}
int main()
{
pr p;
int N, i, j;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
in>>N>>p0;
for(i=1; i < N; ++i)
{
in>>p;
if(p.first < p0.first || (p.first == p0.first && p.second < p0.second))
{
v.push_back(p0);
p0=p;
}
else v.push_back(p);
}
sort(v.begin(), v.end(), cmp);
ConvexHull.push_back(p0);
ConvexHull.push_back(v[0]);
ConvexHull.push_back(v[1]);
for(i=2, N-=1; i < N; ++i)
{
for(j=ConvexHull.size()-1; j && crossProduct(v[i]-ConvexHull[j], ConvexHull[j-1] - ConvexHull[j]) >= error; --j)
ConvexHull.pop_back();
ConvexHull.push_back(v[i]);
}
out<<ConvexHull.size()<<'\n';
copy(ConvexHull.rbegin(), ConvexHull.rend(), ostream_iterator<pr>(out, "\n"));
return EXIT_SUCCESS;
}