Cod sursa(job #610398)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 26 august 2011 23:05:25
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Point
{
	Point()
	{}
	Point(const float xx, const float yy) : x(xx), y(yy)
	{}
	
	inline const bool operator <(const Point& p) const
	{
		return this->x < p.x || (this->x==p.x && this->y<p.y);
	}
	
	float x,y;
};

double CrossProduct(const Point& O, const Point& p1, const Point& p2)
{
	return (p1.x - O.x)*(p2.y - O.y) - (p1.y - O.y)*(p2.x - O.x);
}

int ConvexHull(const vector<Point>& vPoints, vector<Point>& vHull)
{
	int n = vPoints.size(), k=0;
	vHull.resize(n+2);
	
	for (int i=0; i<n; ++i)
	{
		while (k>=2 && CrossProduct(vHull[k-2], vHull[k-1], vPoints[i])<=0)
			k--;
		vHull[k++] = vPoints[i];
	}
	
	int start = k+1;
	for (int i=n-2; i>=0; --i)
	{
		while (k>=start && CrossProduct(vHull[k-2], vHull[k-1], vPoints[i])<=0)
			k--;
		vHull[k++] = vPoints[i];
	}
	
	vHull.resize(k);
	return k;
}

int main()
{
	int n;
	vector<Point> vPoints;
	vector<Point> vHull;
	fstream fin("infasuratoare.in", fstream::in);
	fstream fout("infasuratoare.out", fstream::out);
	
	fin >> n;
	//cout << n << endl;
	
	for (int i=0; i<n; ++i)
	{
		float x,y;
		fin >> x >> y;
		vPoints.push_back(Point(x,y));
		
		//cout << vPoints[i].x << " " << vPoints[i].y << endl;
	}
	//cout << endl;
	
	sort(vPoints.begin(), vPoints.end());
	
	/*for (int i=0; i<n; ++i)
	{
		cout << vPoints[i].x << " " << vPoints[i].y << endl;
	}
	cout << endl;*/
	
	fout << ConvexHull(vPoints, vHull)-1 << "\n";
	
	fout.precision(17);
	for (int i=1; i<vHull.size(); ++i)
	{
		fout << vHull[i].x << " " << vHull[i].y << "\n";
	}
	//cout << "\n";
	
	fin.close();
	fout.close();
	return 0;
}