Pagini recente » Cod sursa (job #1539103) | Cod sursa (job #2109813) | Cod sursa (job #1890746) | Cod sursa (job #1335929) | Cod sursa (job #1251731)
#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';
}