Cod sursa(job #3212873)

Utilizator maiaauUngureanu Maia maiaau Data 12 martie 2024 11:35:35
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pt = pair<double,double>;
#define pb push_back
#define x first 
#define y second

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int N = 12e4+3;

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

int main()
{
    fin >> n; v.resize(n); r.resize(n);
    for (int i = 0; i < n; i++)
        fin >> v[i].x >> v[i].y;

    int i = 0;
    for (int j = 1; j < n; j++)
        if (v[i] > v[j]) i = j;
    swap(v[0], v[i]);

    sort(v.begin() + 1, v.end(), sortTrig);

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

    return 0;
}