Cod sursa(job #3235447)

Utilizator rares89_Dumitriu Rares rares89_ Data 17 iunie 2024 22:58:39
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <fstream>
#include <algorithm>
#define INF 0x3f3f3f3f

using namespace std;
using operative = double;
using pt = pair<operative, operative>;

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


int det(operative X1, operative Y1, operative X2, operative Y2, operative X3, operative Y3) {
    return (X2 - X1) * (Y3 - Y1) - (X3 - X1) * (Y2 - Y1);
}
int cmp(const pt &a, const pt &b) {
    int d = det(0, 0, a.first, a.second, b.first, b.second);
    if (d != 0) {
        return d > 0;
    }
    return a.first * a.first + a.second * a.second > b.first * b.first + b.second * b.second;
}

pt v[103], s[103], aux;
int n, i, j, k, pminim;

int main() {
    fin>>n;
    pminim = 0;
    v[0].first = v[0].second = INF;
    for(i = 1; i <= n; ++i) {
        fin >> v[i].first >> v[i].second;
        if (v[i].second < v[pminim].second ||
            ((v[i].second == v[pminim].second)&&(v[i].first < v[pminim].first) )) {
            pminim = i;
        }
    }
    v[0] = v[pminim];
    v[pminim] = v[1];
    v[1] = v[0];
    for (i = 1; i <= n; ++i) {
        v[i].first -= v[0].first;
        v[i].second -= v[0].second;
    }
    sort(v + 2, v + n + 1, cmp);
    for(j = 3; j <= n; ++j)
        if (det(v[1].first, v[1].second, v[2].first, v[2].second, v[j].first,v[j].second)) {
            break;
        }
    i = 2;
    --j;
    while(i < j) {
        aux = v[i];
        v[i] = v[j];
        v[j] = aux;
        ++i;
        --j;
    }
    s[1] = v[1];
    s[2] = v[2];
    k = 2;
    for(i = 3; i <= n; i++) {
        while(k >= 2 &&
        det(s[k - 1].first, s[k - 1].second, s[k].first, s[k].second, v[i].first, v[i].second) < 0) {
            k--;
        }
        s[++k] = v[i];
    }
    fout << k << "\n";
    for (i = 1; i <= k; ++i) {
        fout << s[i].first + v[0].first << " " << s[i].second + v[0].second << "\n";
    }
    return 0;
}