Cod sursa(job #3030204)

Utilizator maiaauUngureanu Maia maiaau Data 17 martie 2023 15:54:07
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

typedef pair<double, double> pt;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const int N = 120005;

int n, rez[N];
pt v[N];

void init(), read();
inline double det(pt, pt, pt);
inline bool sortTrig(pt, pt);

int main()
{
    init();
    rez[1] = 1; int k = 1;
    for (int i = 2; i < n; i++){
        while (det(v[rez[k - 1]], v[rez[k]], v[i]) <= 0 && k > 1) k--;
        k++; rez[k] = i; 
    }
    g << k + 1 << '\n' << fixed << setprecision(12);
    for (int i = 0; i <= k; i++) g << v[rez[i]].x << ' ' << v[rez[i]].y << '\n';
    
    return 0;
}

void read() {
    f >> n;
    for (int i = 0; i < n; i++)
        f >> v[i].x >> v[i].y;
}
void init(){
    read();
    int lo = 0;
    for (int i = 1; i < n; i++)
        if (v[i] < v[lo]) lo = i;
    swap(v[0], v[lo]);
    sort(v + 1, v + n, sortTrig);
    
}

inline double det(pt a, pt b, pt c){
    return a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y;
}
inline bool sortTrig(pt a, pt b){
    int Det = det(v[0], a, b);
    return (Det > 0);
}