Cod sursa(job #2765732)

Utilizator SerbaP123Popescu Serban SerbaP123 Data 29 iulie 2021 18:01:08
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

const int nmax = 12e4;
const int INF = 2e9;
int s[nmax + 10]; ///pozitiile punctelor care apartin infasuratoarei convexe.
int n, poz;

struct point{
    long double x, y, panta;
}v[nmax + 10], origine;


bool cmp(point a, point b){ ///
    if(a.panta < b.panta){
        return true;
    }
    else if(a.panta == b.panta && a.x < b.x){
        return true;
    }
    return false;
}

int convex(int i, int k){
    point a, b, c;
    a = v[s[k - 1]];
    b = v[s[k]];
    c = v[i];
    double S = (a.x - c.x) * (b.y - a.y) + (a.x - b.x) * (a.y - c.y);
    if(S >= 0){
        return 1;
    }
    return 0;
}

int main(){
    cin >> n;
    origine.x = origine.y = INF;
    for(int i = 1; i <= n; ++i){
        cin >> v[i].x >> v[i].y;
        if(v[i].x < origine.x || v[i].x == origine.x && v[i].y < origine.y){
            origine = v[i];
            poz = i;
        }
    }
    swap(v[1], v[poz]);
    for(int i = 2; i <= n; ++i){
        v[i].panta = (v[i].y - origine.y) / (v[i].x - origine.x);
    }
    sort(v + 2, v + n + 1, cmp);
    s[1] = 1, s[2] = 2;
    int k = 2;
    for(int i = 3; i <= n; ++i){
        while(!convex(i, k) && k > 2){
            k--;
        }
        s[++k] = i;
    }
    cout << k << "\n";
    for(int i = 1; i <= k; ++i){
        cout << fixed << setprecision(6) << v[s[i]].x << " ";
        cout << fixed << setprecision(6) << v[s[i]].y << "\n";
    }
    return 0;
}