Cod sursa(job #666198)

Utilizator hiticas_abelhiticasabel hiticas_abel Data 22 ianuarie 2012 11:32:15
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

const int MAX_N = 120010;//declaram constanta care retine valoarea maxima

#define x first
#define y second
#define punct pair<double, double> //tipul punct va retine coord x si y

int n;
punct a[MAX_N];
int s[MAX_N], viz[MAX_N];

int signum(punct a, punct b, punct c)//returneaza 1 cand det>0 si 0 cand det<=0
{
	return 1 - ((a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y) <= 0);
}

int main()
{
	int i, p,k;
	ifstream f("infasuratoare.in");
	   f>>n;

	for (i = 1; i <= n; ++i)
		 f>>a[i].x>>a[i].y;
      f.close();
       
	sort(a + 1, a + n + 1); //sorteaza elementele vectorului

    k=1;//k numara punctele aflate pe infasuratoare
	s[k] = 1;//s-vector care retine punctele vizitate
	
	for (i = 2, p = 1; i; i=i+ (p = (i == n) ? -p : p))//cand ajunge i la n scade pana la 0
	{
		if (!viz[i])//daca n-am vizitat punctul i
		{
			while (k > 1 && signum(a[i], a[s[k]], a[s[k - 1]]))
				viz[s[k--]] = 0;

			viz[s[++k] = i] = 1;
		}
	}

  ofstream g("infasuratoare.out");	
    g<<k-1<<"\n";
	g<<setiosflags(ios::showpoint)<<setprecision(6);//afiseaza cu 6 cifre dupa virgula

	
	for (i = 1; i < k; ++i)
		g<<a[s[i]].x<<" "<<a[s[i]].y<<"\n";
	
	g.close();
	
	return 0;
}