Cod sursa(job #2511145)

Utilizator Bulboaca_EugenBulboaca Alexandru Eugen Bulboaca_Eugen Data 18 decembrie 2019 13:17:57
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 12*1e4 + 50;
const int INF = 1e8;
const long double EPS = 1e-12;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
    long double x, y, panta;
}p[MAXN];
bool cmp(punct a, punct b){
    return a.panta + EPS < b.panta || (a.panta == b.panta && a.x + EPS< b.x);
}
bool trig(punct a, punct b, punct c){
    return (a.x - c. x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x) < 0 ;
}
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0); fout.tie(0);
    int n, indice = 1; fin >> n;
    for(int i = 1; i <= n; ++i){
        fin >> p[i].x >> p[i].y;
        if(p[i].x < p[indice].x  || (p[i].x == p[indice].x && p[i].y <= p[indice].y))
            indice = i;
    }
    for(int i = 1; i <= n; ++i){
        if(i == indice) continue;
        if(p[i].x == p[indice].x) p[i].panta = INF;
        p[i].panta = (p[i].y - p[indice].y) / (p[i].x - p[indice].x);
    }
    swap(p[1], p[indice]);
    sort(p + 2, p + n + 1, cmp);
    p[n + 1] = p[1];
    deque <int> stiva ;
    int i = 3;
    stiva.push_back(1);
    stiva.push_back(2);
    while(i <= n + 1 and stiva.back() != stiva.front()){
        if(stiva.size() <= 1) stiva.push_back(i);
        else{

            while(stiva.size() >= 1 and trig(p[stiva[stiva.size()- 2]], p[stiva[stiva.size() - 1]], p[i]))
                stiva.pop_back();
            if(!trig(p[stiva[stiva.size() - 2]], p[stiva[stiva.size() - 1]], p[i]))
                stiva.push_back(i);
        }
        ++i;
    }
    fout << stiva.size() - 1<< '\n';
    for(int i = 1; i <= (int)stiva.size() - 1 ; ++i)
        fout << setprecision(7) << fixed << p[stiva[i]].x << " " << p[stiva[i]].y << '\n';
    return 0;
}