Cod sursa(job #803344)

Utilizator VladberilaVladutz Vladberila Data 27 octombrie 2012 13:46:18
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3 kb
// InfasuratoareConvexa.cpp : Defines the entry point for the console application.
//
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

typedef struct  
{
	long double x,y;
} punct;
unsigned int n;
std::vector<punct> m_nPoints;
void solve(std::vector<punct>, std::vector<punct>);
bool cmp(punct a, punct b)
{
	if(a.x < b.x)
		return true;
	if(a.x == b.x)
		if(a.y < b.y)
			return true;
	return false;
}

void read()
{
	FILE* f = NULL;
	fopen("infasuratoare.in", "r");
	fscanf(f, "%u", &n);
	for(unsigned i = 0; i < n; i++)
	{
		punct x;
		fscanf(f, "%Lf%Lf", &x.x, &x.y);
		m_nPoints.push_back(x);
	}
	fclose(f);
}

long double determinant(punct a, punct b, punct c)	//pozitia lui c fata de ab
{
	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

void calculateConvexHull()
{
	std::vector<punct> m_upperPoints;
	std::vector<punct> m_lowerPoints;
	sort(m_nPoints.begin(), m_nPoints.end(), cmp);
	punct p1 = *m_nPoints.begin(), pmax = *(m_nPoints.end() - 1);
	m_lowerPoints.push_back(p1);
	m_upperPoints.push_back(p1);
	for(std::vector<punct>::iterator it = m_nPoints.begin() + 1; it != m_nPoints.end() - 1; it++)
	{
		if(determinant(p1, pmax, *it) > 0)
			m_upperPoints.push_back(*it);
		else
			m_lowerPoints.push_back(*it);
	}
	m_lowerPoints.push_back(pmax);
	m_upperPoints.push_back(pmax);
	solve(m_lowerPoints, m_upperPoints);
}

void solve(std::vector<punct> m_lowerPoints, std::vector<punct> m_upperPoints)
{
	std::stack<punct> upperStack;
	std::stack<punct> lowerStack;
	FILE* g = NULL;
	fopen("infasuratoare.out", "w");

	upperStack.push(m_upperPoints[0]);
	upperStack.push(m_upperPoints[1]);
	for(unsigned i = 2; i < m_upperPoints.size(); i++)
	{
		punct a = m_upperPoints[i];
		punct x = upperStack.top();
		upperStack.pop();
		while(upperStack.empty() == false && determinant(upperStack.top(), a, x) < 0)
		{
			x = upperStack.top();
			upperStack.pop();
		}
		upperStack.push(x);
		upperStack.push(a);
	}

	lowerStack.push(m_lowerPoints[0]);
	lowerStack.push(m_lowerPoints[1]);
	for(unsigned i = 2; i < m_lowerPoints.size(); i++)
	{
		punct a = m_lowerPoints[i];
		punct x = lowerStack.top();
		lowerStack.pop();
		while(lowerStack.empty() == false && determinant(lowerStack.top(), a, x) > 0)
		{
			x = lowerStack.top();
			lowerStack.pop();
		}
		lowerStack.push(x);
		lowerStack.push(a);
	}
	fprintf(g, "%d\n", lowerStack.size() + upperStack.size() - 2);
	unsigned k = lowerStack.size();
	m_lowerPoints.clear();
	for(unsigned i = 0; i < k - 1; i++)
	{
		m_lowerPoints.push_back(lowerStack.top());
		lowerStack.pop();
	}
	for(unsigned i = m_lowerPoints.size() - 1; i >= 0; i--)
		fprintf(g, "%Lf %Lf\n", m_lowerPoints[i].x, m_lowerPoints[i].y);
	upperStack.pop();
	while(upperStack.empty() == false)
	{
		fprintf(g, "%Lf %Lf\n", upperStack.top().x, upperStack.top().y);
		upperStack.pop();
	}
	fclose(g);
}

int main(int argc, char* argv[])
{
	read();
	calculateConvexHull();
	return 0;
}