Cod sursa(job #547239)

Utilizator dacyanMujdar Dacian dacyan Data 6 martie 2011 01:02:11
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define DIM 220000
#define eps 0.000001
using namespace std;

ofstream fout("mosia.out");

struct Punct {
	double x;
	double y;

}a[DIM];

int n, vf, il, pas;
int p[DIM]; // stiva 
bool s[DIM];


void Read();
void Write();
void Hill();
void GasestePunct();

bool Calc(Punct A, Punct B);
int IntoarceDreapta(Punct A, Punct B, Punct C);

int main()
{
	Read();
	sort(a + 1, a + n + 1, Calc);
	
	Hill();

	Write();
	return 0;
}

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




void Hill()
{
	p[++vf] = 1;
	p[++vf] = 2;
	s[2] = 1;
	il = 2;       // contor pt puncte
	pas = 1;
	while ( il > 1 )
	{
		GasestePunct();
		if ( il == 0 ) break;
		while (vf > 1 && IntoarceDreapta(a[p[vf]], a[p[vf-1]], a[il]))
		{
			s[vf] = 0;
			vf--;
		}
		p[++vf] = il;
		s[il] = 1;
	}
}

void GasestePunct()
{
	while ( s[il] )
	{
	    il += pas;
        if (il == n) pas = -1; //daca am ajuns in elementul cu ordonata cea mai mare, ne intoarcem
    }
}




int IntoarceDreapta(Punct A, Punct B, Punct C)
{
	double x1 = A.x;
	double y1 = A.y;
	double x2 = B.x;
	double y2 = B.y;
	double x3 = C.x;
	double y3 = C.y;
	if ((x2-x1) * (y3-y1) - (x3-x1) * (y2-y1) <= 0) return 1;
	return 0;
}



void Write()
{
	ofstream fout("infasuratoare.out");
	fout << vf << '\n';
	for (int i = 1; i <= vf; ++i)
      fout << fixed << setprecision(6) << a[p[i]].x << ' ' << fixed << setprecision(6) << a[p[i]].y << '\n';
 
	fout.close();
}

bool Calc(Punct A, Punct B)
{
	return (A.y < B.y || (A.y == B.y && A.x < B.x));
}