Cod sursa(job #1251800)

Utilizator vlad.florescu94FMI Florescu Vlad - Adrian vlad.florescu94 Data 29 octombrie 2014 21:50:38
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.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 areEqual(double x, double y){
    double diff=x-y;
    if(diff<0)
        return (y-x<limit);
    return diff<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);

//    for(int i=0; i < n ; i++)
//        g<<"("<<points[i].x<<","<<points[i].y<<"),";

   vector<Point> pointsList; int convexHullNumberOfPoints=3;

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

   int auxIndex = 2;
   while(areEqual(Point::determinant(pointsList[0],pointsList[1],points[auxIndex]) , 0 )) // primele 3 sa nu fie coliniare
   {
       //g<<pointsList[0].x<<","<<pointsList[0].y<<"///"<<pointsList[1].x<<","<<pointsList[1].y<<"///"<<points[auxIndex].x<<" "<<points[auxIndex].y<<'\n';
        pointsList[1]=points[auxIndex];
        auxIndex++;
   }

   pointsList.push_back(points[auxIndex]);

   for(int i=auxIndex+1 ; i<n; )
   {
        if(Point::determinant(pointsList[pointsList.size()-2], pointsList[pointsList.size()-1], points[i]) > 0){
            //g<<"BUN: "<<pointsList[pointsList.size()-2].x<<","<<pointsList[pointsList.size()-2].y<<"|"<<pointsList[pointsList.size()-1].x<<","<<pointsList[pointsList.size()-1].y<<"|"<<points[i].x<<","<<points[i].y<<'\n';
            pointsList.push_back(points[i]);
            convexHullNumberOfPoints++;
            i++;
        }
        else{
            //g<<"RAU: "<<pointsList[pointsList.size()-2].x<<","<<pointsList[pointsList.size()-2].y<<"|"<<pointsList[pointsList.size()-1].x<<","<<pointsList[pointsList.size()-1].y<<"|"<<points[i].x<<","<<points[i].y<<'\n';
            pointsList.pop_back();
            convexHullNumberOfPoints--;
        }
   }

   g<<convexHullNumberOfPoints<<'\n';

   g<<fixed;

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

}