Cod sursa(job #2491942)

Utilizator Antonio020712Potra Antonio Antonio020712 Data 13 noiembrie 2019 16:54:50
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct punct {
    float x, y;
};

bool compara(punct a, punct b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

bool cw(punct a, punct b, punct c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
} 

bool ccw(punct a, punct b, punct c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}

void infasuratoare(vector<punct>& v) {
    int i;

    if (v.size() == 1)
        return;

    sort(v.begin(), v.end(), &compara);
    punct minim = v[0], maxim = v.back();

    vector<punct> sus, jos;
    sus.push_back(minim);
    jos.push_back(minim);

    for (i = 1; i < (int)v.size(); i++) {
        if (i == v.size() - 1 || cw(minim, v[i], maxim)) {
            while (sus.size() >= 2 && !cw(sus[sus.size() - 2], sus[sus.size() - 1], v[i]))
                sus.pop_back();
            sus.push_back(v[i]);
        }
        if (i == v.size() - 1 || ccw(minim, v[i], maxim)) {
            while (jos.size() >= 2 && !ccw(jos[jos.size() - 2], jos[jos.size() - 1], v[i]))
                jos.pop_back();
            jos.push_back(v[i]);
        }
    }

    v.clear();
    for (i = 0; i < (int)sus.size(); i++)
        v.push_back(sus[i]);
    for (i = (int)jos.size() - 2; i > 0; i--) // jos.size() - 1 e B, iar jos[0] e A care au fost tiparite 
        v.push_back(jos[i]);                  // in for-ul pentru vectorul sus
}

int main() {
    int n, i;
    punct p;
    vector<punct> v;

    fin >> n;
    for (i = 1; i <= n; i++) {
        fin >> p.x >> p.y;
        v.push_back(p);
    }

    infasuratoare(v);

    fout << fixed << setprecision(6);
    fout << v.size() << '\n';
    for (i = (int)v.size() - 1; i >= 0; i--)
        fout << v[i].x << ' ' << v[i].y << '\n';

    fin.close();
    fout.close();

    return 0;
}