Cod sursa(job #2576495)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 6 martie 2020 19:55:36
Problema Infasuratoare convexa Scor 0
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, [pivot](Point A, Point B){return det(points[pivot], A, B) > 0;});

    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]) == false) --head;

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

    fout << fixed;

    fout << head << '\n';

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