Cod sursa(job #728680)

Utilizator dacyanMujdar Dacian dacyan Data 28 martie 2012 21:16:28
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define DIM 120100
using namespace std;

int n;
pair<double, double> P[DIM];
int St[DIM];
bool s[DIM];
int pas, k, i;

void Read();
void Hill();
void GasestePunct();
int Semn(int, int, int);
bool Calc(pair<double, double>, pair<double, double>);
void Write();

int main()
{
	Read();
	Hill();
	Write();
	return 0;
}

void Read()
{
	ifstream fin("infasuratoare.in");
	fin >> n;
	for (int i = 1; i <= n; ++i)
		fin >> P[i].first >> P[i].second;
	fin.close();
}

void Hill()
{
	sort(P + 1, P + n + 1);
	s[2] = 1;
	St[1] = 1; St[2] = 2;
	k = 2; // varful stivei - punem punctele 0 si 1 in stiva
	i = 2;
	pas = 1;
	while (i > 1)
	{
		GasestePunct();
		if (!i) return;
		while (k > 1 && Semn(St[k-1], St[k], i) == -1)
		{
			s[St[k]] = 0;
			k--;
		}
		St[++k] = i;
		s[i] = 1;
	}
}

void GasestePunct()
{
	while (s[i])
	{
		i += pas;
		if (i == n) pas = -1;
	}
}

int Semn(int A, int B, int C)
{
	double aa = P[A].second - P[B].second;
	double bb = P[B].first - P[B].first;
	double cc = P[A].first * P[B].second - P[B].first * P[A].second;
	double x = P[C].first;
	double y = P[C].second;
	if ((aa * x + bb * y + cc) < 0) return -1;
	return 1;
}

bool Calc(pair<double, double> A, pair<double, double> B)
{
	return A.second < B.second || (A.second == B.second && A.first < B.first);
}

void Write()
{
	ofstream fout("infasuratoare.out");
	fout << k-1  << '\n';
	for (int i = 1; i <= k; ++i)
		fout << fixed << setprecision(12) << P[St[i]].first << ' '
			 << fixed << setprecision(12) << P[St[i]].second << '\n';
	fout.close();
}