Cod sursa(job #1109344)

Utilizator nalexandruIovan Alexandru Nicolae nalexandru Data 17 februarie 2014 00:09:22
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

typedef pair<double, double> Point;
 
Point pMin;

double turns(Point p0, Point p1, Point p2){
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
 
int cmp(Point p1, Point p2) { 
    return turns(pMin, p1, p2) < 0;
}
 
std::vector<Point> convexHull(std::vector<Point> points)
{
    std::vector<Point> convexhull;

    uint pmin = 0;
    for(uint i = 0; i < points.size(); i++){
        if(points[i].y < points[pmin].y){
            pmin = i;
        }
    }

    swap(points[0], points[pmin]);
    pMin = points[0];
    sort(++(points.begin()), points.end(), cmp);

    convexhull.push_back(points[0]);
    convexhull.push_back(points[1]);

    for (uint i = 2; i < points.size(); ++i)
    {
        while (convexhull.size()>=2 && turns(convexhull[convexhull.size() - 2], 
                                              convexhull[convexhull.size() -1], 
                                              points[i])>0 ) 
            convexhull.pop_back();

        convexhull.push_back(points[i]);
    }

    return convexhull;
}
 
std::vector<Point> read()
{
    int N;
    f>>N;
    std::vector<Point> points;
    for (uint i = 0; i < N; ++i)
    {
        double x, y;
        f>>x>>y;
        Point p;
        p.x = x;
        p.y = y;
        points.push_back(p);
    }

    return points;
}

void printP(std::vector<Point> points){
    g<<fixed<<setprecision(9)<<points.size()<<'\n';
    for (int i=0; i < points.size(); i++)
        g<<points[i].x<<' '<<points[i].y<<'\n';
}
 
int main()
{
    printP(convexHull(read()));
    return 0;
}