Cod sursa(job #2287585)

Utilizator tigeraOprea Tereza Emilia tigera Data 22 noiembrie 2018 08:19:30
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define pii pair <double, double>
#define x first
#define y second
#include <iomanip>

using namespace std;

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

vector <pii> v;
int  st[120010], st1[120010];
int n, top, top1;
double a, b;

double det (pii a, pii b, pii c){
    int 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;
    v.push_back({0, 0});
    for (int i=1; i<=n; i++){
        fin >> a >> b;
        v.push_back({a, b});
    }
    sort (v.begin(), v.end());
    st[++top] = 1;
    for (int i=2; i<=n; i++){
        if (top == 1)
            st[++top] = i;
        else{

            while (top >=2 && det (v[st[top-1] ], v[ st[top] ], v[i] )> 0)
                top--;
            st[++top] = i;
        }
    }

    st1[++top1] = n;
    for (int i=n-1; i>=1; i--){
        if (top1 == 1)
            st1[++top1] = i;
        else{

            while (top1 >=2 && det (v[st1[top1-1] ], v[ st1[top1] ], v[i] )> 0)
                top1--;
            st1[++top1] = i;
        }
    }
    fout << top + top1 - 2 << '\n';
    for (int i=top; i>=1; i--)
        fout << setprecision(6) << v[st[i]].x << ' ' << v[st[i]].y << '\n';
    for (int i=top1-1; i>1; i--)
        fout << setprecision(6) <<  v[st1[i]].x << ' ' << v[st1[i]].y << '\n';
    return 0;
}