Cod sursa(job #3142061)

Utilizator DariusM17Murgoci Darius DariusM17 Data 18 iulie 2023 17:24:43
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
//#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map> 
#include <map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <cstring>
#include <assert.h>
#include <iomanip>
using namespace std;
const string file = "infasuratoare";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
#define FAST ios_base::sync_with_stdio(0), cin.tie(0),cout.tie(0) ;
typedef pair<long double, long double>  point;
const int NMAX = 120005;
point v[NMAX];
int n;
long double unghi(point a, point b, point c) {
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}
bool comp(point c, point b) {
    return unghi(v[1], b, c) < 0;
}
vector <point> st;
int main(void)
{
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> v[i].first >> v[i].second;
    int pos = 1;
    for (int i = 1; i <= n; ++i) if (v[pos] > v[i]) pos = i;
    swap(v[1], v[pos]);
    sort(v + 2, v + n + 1,comp);
    st.push_back(v[1]), st.push_back(v[2]);
    for (int i = 3; i <= n; ++i) {
        while (st.size() >= 2 && unghi(st[st.size() - 1], st[st.size() - 2],v[i]) > 0) st.pop_back();
        st.push_back(v[i]);
    }
    cout << st.size() << '\n';
    reverse(st.begin(), st.end());
    for (auto it : st) cout << fixed << setprecision(10) << it.first << " " << it.second << '\n';
    return 0;
}