Cod sursa(job #3197636)

Utilizator devilexeHosu George-Bogdan devilexe Data 27 ianuarie 2024 11:03:47
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 12e4;
pair<long double, long double> P[MAXN];
long double lmx, lmy;
int N, leftmost = -1;
int st[MAXN], k = 0;

long double det(pair<long double, long double> A, pair<long double, long double> B, pair<long double, long double> C)
{
    long double x1, y1, x2, y2, x3, y3;
    tie(x1, y1) = A;
    tie(x2, y2) = B;
    tie(x3, y3) = C;

    return x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3;
}

int main()
{
    fin >> N;
    long double x, y;
    for(int i = 0; i < N; ++i) {
        fin >> x >> y;
        P[i] = make_pair(x, y);
        if(leftmost == -1 || x < lmx || x == lmx && y < lmy) {
            lmx = x;
            lmy = y;
            leftmost = i;
        }
    }
    swap(P[0], P[leftmost]);
    sort(P + 1, P + N, [&](auto a, auto b) {
        return det(P[0], a, b) >= 0;
    });
    st[k++] = 0;
    st[k++] = 1;
    for(int i = 2; i < N; ++i) {
        while(k > 1 && det(P[st[k-2]], P[st[k-1]], P[i]) < 0)
            --k;
        st[k++] = i;
    }
    // trig order
    /*sort(st + 1, st + k, [&](int a, int b) {
        return det(P[0], P[a], P[b]) >= 0;
    });*/
    fout << k << '\n';
    fout << fixed << setprecision(6);
    for(int i = 0; i < k; ++i) {
        tie(x, y) = P[st[i]];
        fout << x << ' ' << y << '\n';
    }
    return 0;
}