Cod sursa(job #415322)

Utilizator recviemAlexandru Pana recviem Data 11 martie 2010 09:45:00
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 4.06 kb
#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;
}