Cod sursa(job #880226)
#include <fstream>
#include <iomanip>
#include <limits>
#include <algorithm>
#include <cmath>
using namespace std;
#define Point pair<double, double>
#define InFile "infasuratoare.in"
#define OutFile "infasuratoare.out"
#define NMax 120000
const double Eps = numeric_limits<double>::epsilon();
const int Precision = 13;
int P, H;
Point points[NMax];
Point hull[NMax];
inline double crossProduct(const Point &p0, const Point &p1, const Point &p2)
{
return (p1.first - p0.first) * (p2.second - p0.second) - (p1.second - p0.second) * (p2.first - p0.first);
}
inline bool minimumCompare(const Point &p1, const Point &p2)
{
return p1.first + Eps < p2.first || abs(p1.first - p2.first) < Eps && p1.second + Eps < p2.second;
}
inline bool angleCompare(const Point &p1, const Point &p2)
{
return crossProduct(points[0], p1, p2) > Eps;
}
inline void clear(int p)
{
while (H >= 2 && crossProduct(hull[H - 2], hull[H - 1], points[p]) + Eps < 0)
{
--H;
}
}
void read()
{
ifstream fin(InFile);
fin >> P;
for (int p = 0; p < P; ++p)
{
fin >> points[p].first >> points[p].second;
}
fin.close();
}
void solve()
{
// Find minimum
swap(*min_element(points, points + P, minimumCompare), points[0]);
// Sort rest of points
sort(points + 1, points + P, angleCompare);
// Insert base elements in hull
hull[H++] = points[0];
hull[H++] = points[1];
// Compute convex hull
for (int p = 2; p < P; ++p)
{
clear(p);
hull[H++] = points[p];
}
}
void write()
{
ofstream fout(OutFile);
fout << H << '\n';
fout.setf(ios::fixed, ios::floatfield);
fout.precision(Precision);
for (int h = 0; h < H; ++h)
{
fout << hull[h].first << ' ' << hull[h].second << '\n';
}
fout.close();
}
int main()
{
read();
solve();
write();
}