#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std::placeholders;

#pragma once
#include <vector>
using namespace std;

// https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

typedef struct Point
{
    double x;
    double y;
};

class Processing
{
public:
    void LoadData(const char* filePath);
    void SaveData(const char* filePath);

    bool Process();

private:
    vector<Point> mPoints;
    vector<Point> mHullResult;

};

double PointsAreCounterClockWise(const Point &p1, const Point &p2, const Point &p3)
{
    double det = p1.x * p2.y - p1.x * p3.y + p2.x * p3.y - p2.x * p1.y + p3.x *p1.y - p3.x * p2.y;
    //return det != abs(det);
    return det;
}

void Processing::LoadData(const char* filePath)
{
    ifstream f(filePath);
    int n;
    f >> n;
    for (int i = 1; i <= n; ++i)
    {
        Point p;
        f >> p.x >> p.y;
        mPoints.push_back(p);
    }
}

void Processing::SaveData(const char* filePath)
{
    ofstream g(filePath);
    g << "Hull size: " << mHullResult.size() << "\n";
    g << setprecision(2) << fixed;
    for (auto p : mHullResult)
    {
        g << "(" << p.x << "," << p.y << ") \n";
    }
}



bool Processing::Process()
{
    LoadData("infasuratoare.in");
    sort(mPoints.begin(), mPoints.end(), 
            [](const Point &p1, const Point &p2)
            {
                if(p1.x != p2.x)
                {
                    return p1.x < p2.x;
                }
                else
                {
                    return p1.y < p2.y;
                }
            });
    for(auto &it: mPoints)
    {

        while(mHullResult.size() >= 3 && (PointsAreCounterClockWise(mHullResult.end()[-2], mHullResult.end()[-1], it) <  0))
        {
            mHullResult.pop_back();
        }
        mHullResult.push_back(it);
    }
    mHullResult.pop_back();

    int nrNewPoints = 0;
    for(auto it = mPoints.rbegin() + 3; it != mPoints.rend(); it++)
    {
        while(nrNewPoints >= 2 && (PointsAreCounterClockWise(mHullResult.end()[-2], mHullResult.end()[-1], *it) < 0))
        {
            mHullResult.pop_back();
            nrNewPoints --;
        }
        mHullResult.push_back(*it);
        nrNewPoints ++;
    }
    mHullResult.pop_back();
    SaveData("infasuratoare.out");
    return true;
}


int main()
{
	auto proc = Processing();
	proc.LoadData("infasuratoare.in");
	proc.Process();
	proc.SaveData("infasuratoare.out");

	return 0;
}