Cod sursa(job #1948824)

Utilizator elffikkVasile Ermicioi elffikk Data 1 aprilie 2017 13:59:36
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

struct pt {
    double x, y;
};
vector <pt> a, h;

double det(pt a, pt b, pt c) {
    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;
}

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

bool cmpAngle(pt p1, pt p2) {
    return det(a[0], p1, p2) < 0;
}

void read() {
    ifstream cin("infasuratoare.in");
    int n;
    cin>>n;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin>>a[i].x>>a[i].y;
    }
}

void write() {
    ofstream cout("infasuratoare.out");
    cout<<h.size()<<"\n";
    for (int i = 0; i < h.size(); i++) {
        cout<<setprecision(12)<<h[i].x<<" "<<h[i].y<<"\n";
    }
}

void solve() {
    swap(*min_element(a.begin(), a.end(), cmpPoint), a[0]);
    sort(a.begin()+1, a.end(), cmpAngle);
    h.push_back(a[0]);
    h.push_back(a[1]);
    for (int i = 2; i < a.size(); i++) {
        while (h.size() > 1 && det(h[h.size()-2], h[h.size()-1], a[i]) > 0) {
            h.erase(h.end()-1);
        }
        h.push_back(a[i]);
    }
    reverse(h.begin(), h.end());
}

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