Cod sursa(job #1773301)

Utilizator elffikkVasile Ermicioi elffikk Data 7 octombrie 2016 18:44:19
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

struct Point {
    double x, y;
};

int n;
vector<Point> a, 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 x, Point y) {
    return det(a[0], x, y)<0;
}

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

void sortPoints() {
    int p = min_element(a.begin(), a.end(), comparePoints) - a.begin();
    swap(a[0], a[p]);
    sort(a.begin()+1, a.end(), compareAngles);
}

void convexHull() {
    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]);
    }
}

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

}

int main() {
    readData();
    sortPoints();
    convexHull();
    writeData();
    return 0;
}