Cod sursa(job #415208)

Utilizator recviemAlexandru Pana recviem Data 10 martie 2010 23:51:44
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.96 kb
#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;
}