Cod sursa(job #2971326)

Utilizator IanisBelu Ianis Ianis Data 27 ianuarie 2023 00:03:13
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#endif

#define endl '\n'

const int NMAX = 120005;

struct Point {
    double x, y;
    bool operator==(const Point &p) {
        return x == p.x && y == p.y;
    }
    bool operator<(const Point &p) {
        if (x == p.x) return y < p.y;
        return x < p.x;
    }
};

int n;
Point a[NMAX];
vector<int> st;

inline double det(const Point &a, const Point &b, const Point &c) {
   return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  // return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
}

void read() {
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> a[i].x >> a[i].y;
    }
}

bool cmp(const Point &p1, const Point &p2) {
  return det(a[1], p1, p2) < 0;
}

void precalc() {
    int pos = 1;
    for (int i = 2; i <= n; i++) {
      if (a[i] < a[pos]) {
        pos = i;
      }
    }
    swap(a[1], a[pos]);
    sort(a + 2, a + n + 1, cmp);
}

void solve() {
    st = {1, 2};

    for (int i = 3; i <= n; i++) {
        if (a[st.back()] == a[i]) continue;
        while (st.size() > 1 && det(a[st[st.size() - 2]], a[st.back()], a[i]) > 0) {
            st.pop_back();
        }
        st.push_back(i);
    }

    fout << st.size() << endl;
    for (int i = 0; i < st.size() - 1; i++) {
        fout << setprecision(6) << fixed << a[st[i]].x << ' ' << a[st[i]].y << endl;
    }
}

int main() {
    read();
    precalc();
    solve();
    return 0;
}