#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <limits>
#include <vector>
using namespace std;
#define FILE_NAME_PATH_LEN 256
const double eps = 1.e-20;
struct point{
double x, y;
};
bool comparePoints (const point &a, const point &b) {
double d1 = (double)b.x - a.x;
if (fabs(d1) < eps) {
double d2 = (double)b.y - a.y;
if (fabs(d2) < eps) {
return true;
} else {
return d2 > 0 ? true : false;
}
} else {
return d1 > 0 ? true : false;
}
}
FILE *infile, *outfile;
double crossprod(point p1, point p2, point p3)
{
return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
vector<point> quickhull(vector<point> PointList, point APoint, point BPoint)
{
vector<point> filteredPoints;
if (PointList.empty()) {
return filteredPoints;
}
point maxDistPoint = PointList.back();
PointList.pop_back();
double maxDistance = crossprod(APoint, BPoint, maxDistPoint);
double crtDistance;
for (point p : PointList) {
crtDistance = crossprod(APoint, BPoint, p);
if (crtDistance >= -eps) {
if (crtDistance - maxDistance > eps) {
if (maxDistance >= -eps) {
filteredPoints.push_back(maxDistPoint);
}
maxDistance = crtDistance;
maxDistPoint = p;
} else {
filteredPoints.push_back(p);
}
}
}
if (maxDistance >= eps) {
vector<point> First, Last;
First = quickhull(filteredPoints, APoint, maxDistPoint);
Last = quickhull(filteredPoints, maxDistPoint, BPoint);
First.push_back(maxDistPoint);
First.insert(First.end(), Last.begin(), Last.end());
return First;
} else {
return vector<point>();
}
}
vector<point> convex_hull(vector<point> PointList)
{
sort(PointList.begin(), PointList.end(), comparePoints);
vector<point> Lower, Upper;
point APoint, BPoint;
APoint = PointList.front();
BPoint = PointList.back();
PointList.erase(PointList.begin());
PointList.pop_back();
/*
for (point p : PointList) {
fprintf(outfile, "%lf %lf\n", (p.x), (p.y));
}
fprintf(outfile, "\n");
*/
Upper = quickhull(PointList, APoint, BPoint);
Lower = quickhull(PointList, BPoint, APoint);
vector<point> res;
res.push_back(APoint);
res.insert(res.end(), Upper.begin(), Upper.end());
res.push_back(BPoint);
res.insert(res.end(), Lower.begin(), Lower.end());
return res;
}
int main()
{
char infilepath[FILE_NAME_PATH_LEN] = "infasuratoare.in";//"./input/input_0.txt";
char outfilepath[FILE_NAME_PATH_LEN] = "infasuratoare.out";//"./output/out_input_0.txt";
infile = fopen(infilepath, "r");
outfile = fopen(outfilepath, "w");
//numeric_limits<double>().epsilon
printf("epsilon %.30lf\n", eps);
point auxpoint;
int inputPointsNum;
vector<point> inputPointList;
fscanf(infile, "%d", &inputPointsNum);
for(int i = 0; i < inputPointsNum; i++) {
fscanf(infile, "%lf %lf", &(auxpoint.x), &(auxpoint.y));
inputPointList.push_back(auxpoint);
}
vector<point> Hullpoints = convex_hull(inputPointList);
fprintf(outfile, "%d\n", Hullpoints.size());
for (point p : Hullpoints) {
fprintf(outfile, "%lf %lf\n", (p.x), (p.y));
}
fprintf(outfile, "\n");
fclose(infile);
fclose(outfile);
return 0;
}