Cod sursa(job #2765659)

Utilizator SerbaP123Popescu Serban SerbaP123 Data 29 iulie 2021 11:13:00
Problema Infasuratoare convexa Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 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 = 1e9;
int s[nmax + 1]; ///pozitiile punctelor care apartin infasuratoarei convexe.
int n, poz;

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


bool cmp(point a, point b){
    if(a.panta == b.panta){
        return a.x < a.y;
    }
    else{
        return a.panta < b.panta;
    }
}

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 == 0 && v[i].y < origine.y){
            origine = v[i];
            poz = i;
        }
    }
    swap(v[poz], v[1]);
    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;
}