Cod sursa(job #1777602)

Utilizator AetheryonStefan Bereghici Aetheryon Data 12 octombrie 2016 18:14:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.01 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
#define Nmax 120013
#define inf 0x3f3f3f3
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

template <class T>
class Point {
    private :
        T x;
        T y;
        T slope;
    public :
        Point(T x,T y){
            this->x = x;
            this->y = y;
        }
        T setX(int x){
            this->x = x;
        }
        T setY(int y){
            this->y = y;
        }
        T setSlope(T slope){
            this->slope = slope;
        }
        T getX(){
            return this->x;
        }
        T getY(){
            return this->y;
        }
        T getSlope(){
            return this->slope;
        }
};

template <class T>
class SetOfPoints {
    private :
        vector <T> points;

        long long leftTurn (T a, T b, T c){
              return (a->getX()*b->getY() - a->getY()*b->getX() +
                      b->getX()*c->getY() - c->getX()*b->getY() +
                      c->getX()*a->getY() - a->getX()*c->getY());
        }

        struct cmp {
            bool operator() (const T &a, const T &b){
                return (a->getSlope()<b->getSlope());
                }
            };

    public :
        SetOfPoints(vector <T> points){
            this->points = points;
        }

        void generateConvexHull(){
            vector <T> ans;
            int index = 0;
            for (int i=1;i<points.size();++i)
                if ((points[index]->getX()>points[i]->getX()) ||
                    (points[index]->getX()==points[i]->getX() && points[index]->getY()>points[i]->getY()))
                        index = i;
            ans.push_back(points[index]);
            swap(points[index],points[0]);
            for (int i=1;i<points.size();++i)
                if (points[i]->getX() == points[0]->getX()) points[i]->setSlope(inf);
                    else points[i]->setSlope(1.00*(points[i]->getY() - points[0]->getY())/(points[i]->getX() - points[0]->getX()));
            sort(points.begin()+1,points.end(),cmp());
            points.push_back(points[0]);
            ans.push_back(points[1]);
            for (int i=2;i<points.size();++i){
                while(!ans.empty() && leftTurn(ans[ans.size()-2],ans[ans.size()-1],points[i])<=0) {
                        ans.pop_back();
                }
                ans.push_back(points[i]);
            }
            ans.pop_back();
            cout<<ans.size()<<"\n";
            for (int i=0;i<ans.size();++i)
                cout<<fixed<<setprecision(12)<<ans[i]->getX()<<" "<<ans[i]->getY()<<"\n";

        }
};

int n;
double x,y;
vector < Point <double>* > p;

int main(){
    cin>>n;
    for (int i=0;i<n;++i){
        cin>>x>>y;
        p.push_back(new Point <double>(x,y));
    }
    SetOfPoints <Point <double>*> *setofpoints = new SetOfPoints <Point <double>*> (p);
    setofpoints->generateConvexHull();
    return 0;
}