Cod sursa(job #580345)

Utilizator dacyanMujdar Dacian dacyan Data 12 aprilie 2011 23:08:09
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.87 kb
/*  ACOPERIREA POLIGONALA (ALG. LUI HILL)

    Se sorteaza punctele in functie de ordonata, iar daca au ordonate egale,
 in functie de abscisa. La fiecare pas se alege cate un punct neselectat, care
 sa formeze cu ultimele 2 puncte puse in stiva un unghi mai mic de 180 grade.
 (avem in vedere faptul ca se formeaza un poligon convex care are masura unui
 unghi interior mai mic de 180 grade).
    In stiva se vor afla punctele ordonate in sens trigonometric, incepand cu
 punctul care are ordonata cea mai mica si abscisa cea mai mica si terminand
 cu acelasi punct.
*/

#include <fstream>
#include <algorithm>
#include <iomanip>
#define maxn 110001
using namespace std;

struct punct {
	double x;
	double y;
} p[maxn], aux;

ofstream fout("infasuratoare.out");

int n;
int sel[maxn]; // sel[i] = 1, daca punctul i a fost selectat
int st[maxn]; // stiva folosita
int i, k, pas;
double aa, bb, cc;

void Read();
void Hill();
void QuickSort(int lf, int rt);
void Modifica();
void GasestePunct();
int Semn(punct A, punct B, punct C);
void Coeficienti(punct A, punct B);
void Write();

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

void Read()
{
	ifstream fin("infasuratoare.in");
	fin >> n;
	for ( i = 1; i <= n; i++ )
		fin >> p[i].x >> p[i].y;
	fin.close();
}
void Hill()
{
    QuickSort(1, n);  // reetichetare a nodurilor
    st[1] = 1;
    st[2] = 2;
    sel[2] = 1;
  	k = 2;       // varful stivei
	i = 2;       // contor pt puncte
	pas = 1;
	while ( i > 1 )
	{
		GasestePunct();
		if ( i == 0 ) break;
		while ( ( k > 1 ) && ( Semn(p[st[k-1]], p[st[k]], p[i]) == -1 ) )
		{
			sel[st[k]] = 0;
			k--;
		}
		k++;
		st[k] = i;
		sel[i] = 1;
    } 
} // a

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

void QuickSort(int lf, int rt)
{
	if ( lf < rt )
	{
		int i = lf - 1, j = rt + 1;
		do
		{
			do
			{
				i++;
			} while ( p[i].y < p[lf].y || ( p[i].y == p[lf].y && p[i].x < p[lf].x ) );
			do
			{
				j--;
			} while ( p[j].y > p[lf].y || ( p[j].y == p[lf].y && p[j].x > p[lf].x ) );
			if ( i < j )
			{
				aux = p[i];
				p[i] = p[j];
				p[j] = aux;
			}
		} while ( i < j );
		QuickSort(lf, j);
		QuickSort(j + 1, rt);
	}
}


int Semn(punct A, punct B, punct C)
{
	Coeficienti(A, B); // calculeaza coeficientii dreptei care trece prin punctele A si B
	if ( aa * C.x + bb * C.y + cc < 0 )
		return -1;  // datorita lui C iese B din stiva
	return 1;
}

void Coeficienti(punct A, punct B)
{
	aa = A.y - B.y;
	bb = B.x - A.x;
	cc = A.x * B.y - B.x * A.y;
}

void Write()
{
	int i = 0;
	fout << k-1 << '\n';
	for ( i = 1; i < k; i++ )
		fout << fixed << setprecision(6) << p[st[i]].x << " " << fixed << setprecision(6) << p[st[i]].y << "\n";
	fout.close();
}