Pagini recente » Cod sursa (job #1045416) | Cod sursa (job #1707801) | Cod sursa (job #2287826) | Cod sursa (job #1431334) | Cod sursa (job #415322)
Cod sursa(job #415322)
#include <vector>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
struct Point{
long double x, y;
Point(long double x, long double y);
Point();
void print();
long double dist(Point p);
long double angleOX();
int operator()(Point a, Point b);
};
struct CcwSort{
Point pivot;
CcwSort(Point f){
pivot = f;
}
// counter clockwise test for 3 points
int ccw(Point p1, Point p2, Point p3){
return (int)((p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x));
}
// compare function
int operator()(Point a, Point b){
return Point(a.x - pivot.x, a.y - pivot.y).angleOX() < Point(b.x - pivot.x, b.y - pivot.y).angleOX();
}
};
class ConvexHull{
public:
vector<Point> points;
void addPoint(Point a);
void printPoints();
int ccw(Point p1, Point p2, Point p3);
vector<Point> getConvexHull();
};
// POINT STRUCTURE
Point::Point(long double newX, long double newY){
// simple constructor
x = newX;
y = newY;
}
Point::Point(){
x = y = 0;
}
inline void Point::print(){
// debug uses mostly
//cout << "Point: " << x << " " << y << " | " << angleOX() << "\n";
cout << x << " " << y << "\n";
}
inline long double Point::dist(Point p){
// euclidian distance between two points
return sqrt( (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));
}
inline long double Point::angleOX(){
const long double pi = 3.14159;
const long double eps = 0.00001;
long double arg = abs((y+eps) / (x+eps));
// quadrants not ftw
if ( x>=0 && y>=0 )
return atan( arg );
if ( x<0 && y>0 )
return pi - atan( arg );
if ( x<0 && y<0 )
return 3*pi / 2 - atan( arg );
return 2*pi - atan( arg );
}
// CONVEX HULL
void ConvexHull::addPoint(Point a){
this->points.push_back(a);
}
void ConvexHull::printPoints(){
for (vector<Point>::iterator it = this->points.begin(); it < this->points.end(); it++)
cout << it->x << " " << it->y << " | " << Point(it->x - this->points[0].x, it->y - this->points[0].y).angleOX() << "\n";
}
void printVector(vector<Point> v){
cout << "[";
for (vector<Point>::iterator it = v.begin(); it != v.end(); it++)
cout << "(" << it->x << "," << it->y << "); ";
cout << "] \n";
}
vector<Point> ConvexHull::getConvexHull(){
vector<Point>::iterator it;
vector<Point> rez;
// find the lowest point
/*
int min = 0;
for (it = this->points.begin(); it < this->points.end(); it++)
if ( it->y < this->points[min].y )
min = it - this->points.begin();
// swap it with the first point
Point aux = this->points[min];
this->points[min] = this->points[0];
this->points[0] = aux;
*/
// sort the points ccw relative to the first point
CcwSort cmp = CcwSort(this->points[0]);
sort(this->points.begin()+1, this->points.end(), cmp);
// walk the points
this->points.push_back(this->points[0]);
rez.push_back(this->points[0]);
rez.push_back(this->points[1]);
int i = 2;
while ( i < this->points.size() ){
int M = rez.size()-1;
//printVector(rez);
while (this->ccw(rez[M-1], rez[M], this->points[i]) < 0){
//cout << "(-): "; rez[M].print();
rez.pop_back();
M = rez.size()-1;
}
rez.push_back(this->points[i]);
//cout << "(+): "; this->points[i].print();
i++;
}
this->points.pop_back();
rez.pop_back();
return rez;
}
int ConvexHull::ccw(Point p1, Point p2, Point p3){
return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}
ConvexHull H;
void citire(){
freopen("points.txt", "r", stdin);
int n;
long double a, b;
scanf("%d", &n);
int min = 0;
for (int i = 0; i<n; i++){
scanf("%lf %lf\n", &a, &b);
H.addPoint(Point(a, b));
if (b < H.points[min].y)
min = i;
}
Point aux = H.points[min];
H.points[min] = H.points[0];
H.points[0] = aux;
}
int main(){
citire();
freopen("infasuratoare.out","w",stdout);
vector<Point> hull = H.getConvexHull();
printf("%d\n", hull.size());
for (vector<Point>::iterator it = hull.begin(); it!=hull.end();it++)
printf("%lf %lf\n", it->x, it->y);
return 0;
}