Cod sursa(job #2564313)

Utilizator Bulboaca_EugenBulboaca Alexandru Eugen Bulboaca_Eugen Data 1 martie 2020 20:05:58
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>
using namespace std;

#define zero(x) (x & (-x))
#define ll long long

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

const int  MAXN = 120000 + 3;
const double EPS = 1e-12;
const long double INF = 1e8;

struct punct{
    long double x, y, panta;
}v[MAXN];

int indice = 1;

bool operatie(punct a, punct b, punct c){
    return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x) >= 0;
}
bool cmp(punct a, punct b){
    return a.panta < b.panta;
}

int main(){
    int n; fin >> n;
    for(int i = 1; i <= n; ++i){
        fin >> v[i].x >> v[i].y;
        if(v[i].x < v[indice].x || (v[i].x == v[indice].x and v[i].y < v[indice].y))
            indice = i;
    }
    swap(v[1], v[indice]);
    for(int i = 2; i <= n; ++i){
        if(v[i].x == v[1].x) v[i].panta = INF;
        else v[i].panta = (v[i].y - v[1].y) / (v[i].x - v[1].x);
    }
    sort(v + 2, v + n + 1, cmp);
    v[n + 1] = v[1];
    deque <int> stiva;
    int i = 3;
    stiva.push_back(1);
    stiva.push_back(2);
    while(i <= n + 1 and stiva.back() != stiva.front()){
        while(stiva.size() >= 2 and !operatie(v[stiva[stiva.size()- 2]], v[stiva[stiva.size()- 1]], v[i]))
            stiva.pop_back();
        stiva.push_back(i++);
    }
    fout << stiva.size() - 1 << '\n' ;
    for(int i = 0; i <= stiva.size() - 2; ++i)
        fout << setprecision(6) << fixed << v[stiva[i]].x << " " << v[stiva[i]].y << '\n';
    return 0;
}