Cod sursa(job #2576525)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 6 martie 2020 20:11:51
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
using namespace std;

typedef pair<long double, long double> Point;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int N_MAX = 12e4 + 1;


int N;
vector<Point> points(N_MAX);

inline bool det(Point& A, Point& B, Point& C){ return (A.first*B.second + B.first*C.second + C.first*A.second - B.second*C.first - C.second*A.first - A.second*B.first) > 0;}

int head;
vector<Point> points_stack(N_MAX);

int main()
{
    fin >> N;

    int pivot = 1;

    for(int i = 1; i <= N; ++i)
    {
        fin >> points[i].first >> points[i].second;

        if(points[i] < points[pivot]) pivot = i;
    }

    swap(points[1], points[pivot]);

    sort(points.begin() + 2, points.begin() + N + 1, [](Point& A, Point& B){return det(points[1], A, B) == false;});

    points_stack[1] = points[1];
    points_stack[2] = points[2];

    head = 2;

    for(int i = 3; i <= N; ++i)
    {
        while(head >= 2 && det(points_stack[head - 1], points_stack[head], points[i]) == true) --head;

        points_stack[++head] = points[i];
    }

    fout << fixed;

    fout << head << '\n';

    for(int i = head; i >= 1; --i)
        fout << setprecision(6) << points_stack[i].first << ' ' << points_stack[i].second << '\n';
}