Cod sursa(job #711250)

Utilizator hunter_ionutzzzFarcas Ionut hunter_ionutzzz Data 11 martie 2012 19:33:03
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("infasu.in");
ofstream fout("infasu.out");
typedef struct{double x,y;}cel;

int i,n,ninf=1,nsup=1;
vector <cel> inf;
vector <cel> sup;
double sarrus(cel a,cel b,cel c)
{  return (a.x*b.y)+(b.x*c.y)+(c.x*a.y)-(c.x*b.y)-(c.y*a.x)-(a.y*b.x);
}
int cmp(cel a,cel b)
{   if (a.x < b.x)
		return 1; 
    else 
		return 0;
}
void citire()
{cel v[10001],pinf,psup;
 int ipsup,ipinf;
    fin >> n;
    pinf.x = 1000000000;
	psup.x = -1000000000;
    for (i=1;i<=n;++i)
	{	fin >> v[i].x >> v[i].y;
	    if (pinf.x > v[i].x)
		{	pinf = v[i];
		    ipinf = i;
		}
		if (psup.x < v[i].x)
		{	psup = v[i];
		    ipsup = i;
		}
	}
	inf[1] = v[ipinf];
	sup[1] = v[ipsup];
	for (i=1;i<=n;++i)
		if (i != ipinf && i != ipsup)
			if (0 > sarrus(v[ipinf],v[ipsup],v[i]))
	    	{	++ninf;
	    	    inf[ninf] = v[i];
            }
            else		
		    {	++nsup;
		    	sup[nsup] = v[i];
    		}
	++nsup;
	sup[nsup] = pinf;
	++ninf;
	inf[ninf] = psup;
	sort(sup+1,sup+1+nsup,cmp);
	sort(inf+1,inf+1+ninf,cmp);
}
void infasuratoare()
{int ok,i,j;
    do
    {   ok = 0;
		i = 2;
		while (i < nsup)
		    if (sarrus(sup[i-1],sup[i+1],sup[i]) > 0)
				++i;
			else
			{   ok = 1;
			    for (j=i;j<=nsup;++j)
					sup[j] = sup[j+1];
				--nsup;
		    }
	}while(ok);
	do
    {   ok = 0;
		i = 2;
		while (i < ninf)
		    if (sarrus(inf[i-1],inf[i+1],inf[i]) < 0)
				++i;
			else
			{   ok = 1;
			    for (j=i;j<=ninf;++j)
					inf[j] = inf[j+1];
				--ninf;
		    }
	}while(ok);
    for (i=nsup-1;i>=2;--i)
    {   ++ninf;
        inf[ninf] = sup[i];
    }
}
int main()
{   citire();
	infasuratoare();
	for (i=1;i<=ninf;++i)
		fout << inf[i].x << " ";
	fout << '\n';
	for (i=1;i<=ninf;++i)
		fout << inf[i].y << " ";
	return 0;
}