Pagini recente » Cod sursa (job #1859559) | Cod sursa (job #1884458) | Cod sursa (job #1045424) | Cod sursa (job #830738) | Cod sursa (job #415208)
Cod sursa(job #415208)
#include <vector>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
struct Point{
double x, y;
Point(double x, double y);
Point();
void print();
double dist(Point p);
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(double newX, 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 double Point::dist(Point p){
// euclidian distance between two points
return sqrt( (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));
}
double absolute(double x){
return x>0?x:-1*x;
}
inline double Point::angleOX(){
const double pi = 3.14159;
const double eps = 0.000001;
double arg = absolute((y+eps) / (x+eps));
// quadrants not ftw
if ( x>=0 && y>=0 )
return atan2( y+eps, x+eps );
if ( x<0 && y>0 )
return atan2( y+eps, x+eps );
if ( x<0 && y<0 )
return atan2( y+eps, x+eps );
return atan2( y+eps, x+eps );
}
// 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("infasuratoare.in", "r", stdin);
int n;
double a, b;
scanf("%d", &n);
for (int i = 0; i<n; i++){
scanf("%lf %lf\n", &a, &b);
H.addPoint(Point(a, b));
}
}
int main(){
ofstream fout("infasuratoare.out");
citire();
vector<Point> hull = H.getConvexHull();
cout << hull.size() << "\n";
for (vector<Point>::iterator it = hull.begin(); it != hull.end(); it++)
cout << it->x << " " << it->y << "\n";
return 0;
}