Cod sursa(job #2105948)

Utilizator Alex18maiAlex Enache Alex18mai Data 14 ianuarie 2018 17:46:53
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

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

struct POINT{
    long double x , y;
} point[120100];

bool cmp (POINT a , POINT b){
    if (a.x == b.x){
        return a.y < b.y;
    }
    return a.x < b.x;
}

vector <POINT> down;
vector <POINT> up;

long double det (POINT a , POINT b , POINT c){
    return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin>>n;

    for (int i=1; i<=n; i++){
        cin>>point[i].x>>point[i].y;
    }

    sort(point + 1, point + n + 1 , cmp);

    for (int i=1; i<=n; i++){

        while (down.size() > 1 && det(down[down.size()-2] , down[down.size()-1] , point[i]) <= 0){
            down.pop_back();
        }
        down.push_back(point[i]);
    }

    for (int i=n; i>=1; i--){

        while (up.size() > 1 && det(up[up.size()-2] , up[up.size()-1] , point[i]) <= 0){
            up.pop_back();
        }
        up.push_back(point[i]);
    }

    cout<<down.size() + up.size() - 2<<'\n';

    for (int i=0; i<down.size()-1; i++){
        cout<<setprecision(12)<<fixed<<down[i].x<<" "<<down[i].y<<'\n';
    }

    for (int i=0; i<up.size()-1; i++){
        cout<<setprecision(12)<<fixed<<up[i].x<<" "<<up[i].y<<'\n';
    }

    return 0;
}