Cod sursa(job #1248683)

Utilizator dan.ghitaDan Ghita dan.ghita Data 25 octombrie 2014 20:03:14
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");



typedef pair<double,  double> Punct;
#define x first
#define y second
//class Punct;
//double determinant(const Punct&, const Punct&, const Punct&);
vector<Punct> v, stck;

//class Punct{
//public:
//    double x, y;
//    Punct(double x, double y):x(x), y(y){};
//
//};

double determinant(const Punct &a, const Punct &b, const Punct &c){
     return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
//    return a.x * b.y + b.x * c.y + c.x * a.y -
//           b.y * c.x - c.y * a.x - a.y * b.x;
}

bool cmp(const Punct& a, const Punct& b){
        return determinant(v[0], a, b) > 0;
}

void infasuratoare(){
    stck.push_back(v[0]);
    stck.push_back(v[1]);

    for(int i = 2; i < v.size(); ++i){
        while(stck.size() > 1 && determinant(stck[stck.size() - 2], stck.back(), v[i]) < 0)
            stck.pop_back();
        stck.push_back(v[i]);
    }


}


int main()
{
    int n;
    double x, y;
    f>>n;
    Punct p;
    while(n--){
        f>>p.x>>p.y;

        v.push_back(p);
    }

//    double mnx = v[0].x, mny = v[0].y;

    int pos = 0;
    for(int i = 1; i < v.size(); ++i)
            if(v[i] < v[pos])
                pos = i;
            swap(v[0], v[pos]);
//        if(v[i].x < mnx)
//            mnx = v[i].x, mny = v[i].y, swap(v[0], v[i]);
//        else
//            if(fabs(v[i].x - mnx) < 0.0000000001 && v[i].y < mny)
//                mnx = v[i].x, mny = v[i].y, swap(v[0], v[i]);


    sort(v.begin()+1, v.end(), cmp);

    infasuratoare();


//    for(int i = 0; i < v.size(); ++i)
//        cout<<setprecision(9)<<v[i].x<<' '<<v[i].y<<'\n';

    g<<stck.size()<<'\n';
    for(int i = 0; i < stck.size(); ++i)
        g<<setprecision(9)<<stck[i].x<<' '<<stck[i].y<<'\n';


    return 0;
}