Cod sursa(job #2827593)

Utilizator StefanSanStanescu Stefan StefanSan Data 5 ianuarie 2022 22:14:44
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int MAX = 120001;

struct point {
    long double x, y;
}a[MAX];

int n, st[MAX], p;

inline long double cross_product(point a, point b, point c) {
    return -(a.x * b.y + c.x * a.y + b.x * c.y - c.x * b.y - a.x * c.y - b.x * a.y);
}

bool comp(point A, point B) {
    return cross_product(a[1], A, B) > 0;
}

int main(){
    
    in >> n;

    int firstPoint = 1;
    for (int i = 1; i <= n; i++) {
        in >> a[i].x >> a[i].y;
        if (a[firstPoint].y > a[i].y || (a[firstPoint].y == a[i].y && a[firstPoint].x > a[i].x))
            firstPoint = i;
    }

    point aux = a[1];
    a[1] = a[firstPoint];
    a[firstPoint] = aux;

    sort(a + 2, a + n + 1, comp);

    /*
    for (int i = 1; i <= n; i++)
        cout << a[i].x << ' ' << a[i].y << '\n';
    */

    st[++p] = 1;
    st[++p] = 2;

    for (int i = 3; i <= n; i++) {
        while (p >= 2 && cross_product(a[st[p - 1]], a[st[p]], a[i]) < 0) 
            p--;
        st[++p] = i;
    }

    out << p << '\n';

    out << fixed << setprecision(12);
    out << a[st[1]].x << ' ' << a[st[1]].y << '\n';
    for (int i = p; i >= 2; i--)
        out << a[st[i]].x << ' ' << a[st[i]].y << '\n';

    return 0;
}