Cod sursa(job #547240)

Utilizator dacyanMujdar Dacian dacyan Data 6 martie 2011 01:09:07
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.05 kb
#include <fstream>
#include <iostream>
#include <cmath>
using namespace std;

#define DIM 130000
#define eps 0.001

struct Punct{
	double x, y;
} a[DIM], aux;

int st[DIM];
int n, nrvf;     //nr total de Puncte, nr de vf ale invelitorii convexe
double minx = 1e+10, miny = 1e+10;

void Citeste();
void Sort();
double Unghi(int);
double Raza(int);
int Conditie(int,int);
void Graham();
int IntoarcereDreapta(int);
void Afis();

int main()
{
	Citeste();
	Sort();
	Graham();
	Afis();

	return 0;
}

void Citeste()
{
	ifstream fin("conv.in");
	fin >> n;
	int i, pmin;
	for (i = 1; i <= n; i++)
	{
		fin >> a[i].x >> a[i].y;
		if ( fabs(a[i].y - miny) < eps && a[i].x < minx) // la aceeasi ordonata conteaza abscisa
		{
			minx = a[i].x;
			pmin = i;
		}
		else if (a[i].y < miny)
		{
			minx = a[i].x;
			miny = a[i].y;
			pmin = i;
		}
	}
	aux = a[pmin];   //plasam primul element din invelitoare in pozitia 1
	a[pmin] = a[1];
	a[1] = aux;      // elem de ordonata minima
	fin.close();
}

// Never 
void Sort() // sortare dupa unghiul polar si la acelasi unghi, dupa raza polara        
{
	int i, j;
	for(i = 2; i < n; i++)
		for(j = i + 1; j <= n; j++)
		{
			if (Conditie(i, j))
			{
				aux = a[i];
				a[i] = a[j];
				a[j] = aux;
			}
		}
}

int Conditie(int i, int j)
{
    if ( fabs(Unghi(i) - Unghi(j)) < eps && Raza(i) > Raza(j))  //daca unghiurile sunt egale ordonam dupa raza
		return 1;
    if (Unghi(i) > Unghi(j))
        return 1;
    return 0;
}

double Unghi(int i)
{
    double yi, xi;
    yi = a[i].y - miny;
    xi = a[i].x - minx;
	if (fabs(xi) < eps)   // a[i].x == minx  => Punctele sunt pe aceeasi verticala
		return 90;
	if (xi > 0)
        return (180 * (atan(yi/xi) / M_PI));
    return (180 - fabs(180 * (atan(yi/xi) / M_PI)));
}

double Raza(int i)
{
    double yi, xi;
	yi = a[i].y - miny;
    xi = a[i].x - minx;
    return sqrt(xi*xi + yi*yi);  // era ma bine fara radical (compari razele la patrat)
}

void Graham()
{
    int i;
    st[0] = 1;    //primele trei Puncte se introduc in stiva
    st[1] = 2;
    st[2] = 3;
    nrvf = 2;
	for (i = 4; i <= n; i++)  //introducem, in ordine, toate cele n-3 Puncte ramase
    {
        while (IntoarcereDreapta(i))
            st[nrvf--] = 0;       // scoatem din stiva toate punctele fata de care varful i "se intoarce la dreapta"
        st[++nrvf] = i;
    }
}

int IntoarcereDreapta(int i)   //calculam cu ajutorul produsului vectorial semnul sinusului
{
    double x1, y1, x2, y2;
    x1 = a[st[nrvf]].x - a[st[nrvf-1]].x;
    y1 = a[st[nrvf]].y - a[st[nrvf-1]].y;
    x2 = a[i].x-a[st[nrvf-1]].x;
    y2 = a[i].y-a[st[nrvf-1]].y;
    if(x1 * y2 - x2 * y1 <= 0)    // nici coliniaritate nu se accepta (<= nu <)
        return 1;
    return 0;
}

void Afis()
{
    ofstream fout("conv.out");
    int i;

    for (i = 0; i <= nrvf; i++)
       fout << a[st[i]].x << " " << a[st[i]].y << '\n';

/*    
    for (i = 1; i <= n; i++)
        fout << a[i].x << " " << a[i].y << '\n';
*/
    fout.close();
}