Cod sursa(job #3000760)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 12 martie 2023 20:18:28
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include<bits/stdc++.h>
#define DIM 1000001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair <double, double> v[DIM], st[DIM], aux;
int pmin, i, j, n, k;
double det(double X1, double Y1, double X2, double Y2, double X3, double Y3){
    return (X2 - X1) * (Y3 - Y1) - (X3 - X1) * (Y2 - Y1);
}
bool cmp(const pair <double, double> &a, const pair <double, double> &b){
    double d = det(0, 0, a.first, a.second, b.first, b.second);
    if(d != 0)
        return d > 0;
    else return a.first * a.first + a.second * a.second > b.first * b.first + b.second * b.second;
}
int main(){
    fin >> n;
    v[pmin].first = DIM;
    v[pmin].second = DIM;
    for(i=1;i<=n;i++){
        fin >> v[i].first >> v[i].second;
        if(v[i].second < v[pmin].second || (v[i].second == v[pmin].second && v[i].first < v[pmin].first))
            pmin = i;
    }
    v[0] = v[pmin];
    v[pmin] = v[1];
    v[1] = v[0];
    for(i=1;i<=n;i++){
        v[i].first -= v[0].first;
        v[i].second -= v[0].second;
    }
    sort(v + 2, v + n + 1, cmp);
    for(j=3;j<=n;j++)
        if(det(v[1].first, v[1].second, v[2].first, v[2].second, v[j].first, v[j].second))
        break;
    i = 2;
    j--;
    while(i < j){
        aux = v[i];
        v[i] = v[j];
        v[j] = aux;
        i++;
        j--;
    }
    st[1] = v[1];
    st[2] = v[2];
    k = 2;
    for(i=3;i<=n;i++){
        while(k >= 2 && det(st[k - 1].first, st[k - 1].second, st[k].first, st[k].second, v[i].first, v[i].second) < 0)
            k--;
        st[++k] = v[i];
    }
    fout << k << "\n";
    for(i=1;i<=k;i++)
        fout << fixed << setprecision(12) << st[i].first + v[0].first << " " << fixed << setprecision(12) << st[i].second + v[0].second << "\n";
}