Pagini recente » Borderou de evaluare (job #2336832) | Cod sursa (job #905424) | Borderou de evaluare (job #2598451) | Borderou de evaluare (job #2492094) | Cod sursa (job #1251800)
#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';
}