Cod sursa(job #1879654)

Utilizator ImGeluGelu Ungur ImGelu Data 15 februarie 2017 08:35:50
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda becreative16 Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Point {
    double x, y;
};

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

vector<Point> v, h;

double det(Point a, Point b, Point c) {
    return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}

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

bool compareAngles(Point a, Point b) {
    return det(v[0], a, b) < 0;
}

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

void read() {
    int n;
    cin>>n;
    v.resize(n);
    for (int i = 0; i < n; i++) {
        cin>>v[i].x>>v[i].y;
    }
}

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

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