Cod sursa(job #2439334)

Utilizator bluestorm57Vasile T bluestorm57 Data 15 iulie 2019 17:49:16
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

typedef pair<double, double> Point;

const int NMAX = 120005;
const int inf = 1000000006;
int n, head;
Point Stack[NMAX], v[NMAX];

double cross_product(const Point &X, const Point &Y, const Point &Z){
    return (Y.first - X.first) * (Z.second - X.second) - (Y.second - X.second) * (Z.first - X.first);
}

bool cmp(const Point &X, const Point &Y){
    return cross_product(v[1], X, Y) < 0;
}

void sort_points(){
    int pos = 1,i;
    for(i = 2 ; i <= n ; i++)
        if(v[i] < v[pos])
            pos = i;

    swap(v[1], v[pos]);

    sort(v + 2, v + n + 1, cmp);
}

int main(){
    int i;
    f >> n;
    for(i = 1 ; i <= n ; i++)
        f >> v[i].first >> v[i].second;

    sort_points();
    Stack[1] = v[1];
    Stack[2] = v[2];
    head = 2;
    for(i = 3 ; i <= n; i++){
        while(head >= 2 && cross_product(Stack[head - 1], Stack [head], v[i]) > 0)
            head--;
        Stack[++head] = v[i];
    }

    g << head << "\n";
    for(i = head ; i >= 1 ; i--)
        g << fixed << setprecision(6) << Stack[i].first << " " << Stack[i].second << "\n";


    return 0;
}