Cod sursa(job #1251731)

Utilizator vlad.florescu94FMI Florescu Vlad - Adrian vlad.florescu94 Data 29 octombrie 2014 20:53:51
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<iomanip>

using namespace std;

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

const double limit = 1e-12;

bool areEquals(double x, double y){
    return (x-y<limit || y-x<limit) ;
}

class Point{
public:
    double x,y;
    static Point pointReference;

    Point(double x=0, double y=0) : x(x), y(y){}

    static double determinant(const Point &a,const Point &b,const Point &c);

    bool operator<(const Point& p) const{
       return (determinant(*this, pointReference, p) > 0);
    }

    Point& operator=(const Point &p)
    {
        x=p.x; y=p.y;
        return *this;
    }

};
Point Point::pointReference;
double Point::determinant(const Point &a, const Point &b, const Point &c)
{
    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);
}

int main()
{
   int n, firstElementPosition;
   double x,y ,xmin=10000000001, ymin=1000000001;

   f>>n;

   Point points[n];

   for(int i=0;i<n; i++)
   {
       f>>x>>y;
       if(x<xmin && y<ymin){
          xmin=x; ymin=y;;
          firstElementPosition=i;
       }

       points[i] = Point(x,y);
   }

   Point::pointReference = Point(xmin, ymin);

   swap(points[0], points[firstElementPosition]);

   sort(points+1, points + n);

   vector<Point> pointsList; int convexHullNumberOfPoints=3;

   pointsList.push_back(points[0]); pointsList.push_back(points[1]); pointsList.push_back(points[2]);

   for(int i=3 ; i<n; )
   {
        if(Point::determinant(pointsList[pointsList.size()-2], pointsList[pointsList.size()-1], points[i])<0){
            pointsList.push_back(points[i]);
            convexHullNumberOfPoints++;
            i++;
        }
        else{
            pointsList.pop_back();
            convexHullNumberOfPoints--;
        }
   }

   g<<fixed;

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

}