Cod sursa(job #496989)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 31 octombrie 2010 22:14:01
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<double,double> dot;
vector<dot> v;

double crossProduct(dot p1, dot p2, dot p)
{
	dot a = make_pair(p1.first - p.first, p1.second - p.second);
	dot b = make_pair(p2.first - p.first, p2.second - p.second);

	return a.first * b.second - a.second * b.first;
}

bool turnsRight(dot p1, dot p2, dot p)
{
	return crossProduct(p1, p2, p) < 0;
}

vector<dot> convexHull(vector<dot> &points)
{
	vector<dot> convexPoints;

	sort(points.begin(), points.end());
	
	convexPoints.push_back(points[0]);
	convexPoints.push_back(points[1]);

	for (int i = 2; i < points.size(); ++i)
	{
		while (convexPoints.size() > 2 && turnsRight(convexPoints[convexPoints.size() - 2], points[i], convexPoints[convexPoints.size() - 1]))
			convexPoints.pop_back();
		convexPoints.push_back(points[i]);
	}

	for (int i = points.size() - 2; i >= 0; --i)
	{
		while (convexPoints.size() > 2 && turnsRight(convexPoints[convexPoints.size() - 2], points[i], convexPoints[convexPoints.size() - 1]))
			convexPoints.pop_back();
		convexPoints.push_back(points[i]);
	}
	convexPoints.pop_back();

	return convexPoints;
}

void readPoints(vector<dot> &pointList, string inputFile)
{
	fstream f(inputFile, ios::in);

	int n;
	f >> n;

	while (n-- > 0)
	{
		double a, b;

		f >> a >> b;
		pointList.push_back(make_pair(a,b));
	}
}

void printPoints(vector<dot> &pointList, string outputFile)
{
	fstream f(outputFile, ios::out);

	f << pointList.size() << "\n";

	for (int i = 0; i < pointList.size(); ++i)
		f << pointList[i].first << " " << pointList[i].second << "\n";
}

int main()
{
	vector<dot> answer;
	readPoints(v, "infasuratoare.in");
	answer = convexHull(v);
	printPoints(answer, "infasuratoare.out");
	return 0;
}