Pagini recente » Cod sursa (job #3204450) | Cod sursa (job #755032) | Cod sursa (job #2017509) | Cod sursa (job #1178034) | Cod sursa (job #1777596)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
const int Nmax = 120013;
#define inf 0x3f3f3f3
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
template <class T>
class Point {
private :
T slope;
T x;
T y;
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 :
int cnt;
vector <T> points;
int 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;
// we find the point with the minimal X-coordinate
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;
// we have a point
ans.push_back(points[index]);
swap(points[index],points[0]);
// precalculate the slopes
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 them by slope
sort(points.begin()+1,points.end(),cmp());
// complete the vector
points.push_back(points[0]);
// init stack
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]);
}
cout<<ans.size()-1<<"\n";
for (int i=0;i<ans.size()-1;++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;
}