Cod sursa(job #2297202)

Utilizator tigeraOprea Tereza Emilia tigera Data 5 decembrie 2018 15:59:09
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct punct{double x,y; } v[120010];
int  st[120010];
int n, top;

int comp (punct a, punct b)
{
    if (a.x < b.x)
    {
        if (a.y < b.y)
            return 1;
        return 0;
    }
    return 0;
}

double det (punct a, punct b, punct c){
    double  ans = a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y -  b.x * a.y;
    return ans;
}

int main()
{
    fin >> n;
    for (int i=1; i<=n; i++){
        fin >> v[i].x >> v[i].y;
    }
    sort (v+1, v + n + 1, comp);
    
    st[1] = 1;
    st[2] = 2;
    top = 2;
    for (int i=3; i<=n; i++){
        while (top >=2 && det (v[st[top-1] ], v[ st[top] ], v[i] ) > 0)
                top--;
            st[++top] = i;
    }
    for (int i=n-1; i>=1; i--){
        while (top >=2 && det (v[st[top-1] ], v[ st[top] ], v[i] ) > 0)
                top--;
        st[++top] = i;
        
    }
    fout << top - 1 << '\n';
    for (int i=top-1; i>=1; i--)
        fout << setprecision(6) << v[st[i]].x << ' ' << v[st[i]].y << '\n';

    fin.close();
    fout.close();
    return 0;
}