1071 Hawaii

[•Marius]

Aici puteţi discuta despre problema Hawaii.

[•ciprianf]

O problema asemanatoare s-a dat la "Elite 2010 U S Open Competition" de pe USACO 

[•Cosmin]

Problema am propus-o pentru Google Code Jam in 2008, nu s-a folosit atunci pt ca aveam prea multe probleme cu triunghiuri anul respectiv si am dat-o aici. Dar imi place cum gandesti

[•Bogdan_tmm]

Se poate imbunatatii cumva timpul functiei atan2? Sau mai exista vreo metoda asemanatoare?
Vreau sa sortez punctele in jurul closcai

[•andrei.12]

Încearcă să îți construiești un alt vector B, în care B[ i ] să rețină deja arctangenta calculată pentru punctul i, și apoi sortează direct vectorul acesta, folosind sort (fără altă funcție de comparare).

[•Bogdan_tmm]

Frumos Hai ca o sa ma apuc sa scriu. Intre timp am facut un fel de atan2 de mana =)) dar iau 2 WA. Creca omit vreun caz.

Cod:

inline bool cmp(p a,p b)
{
	ld adx=a.first-fix.first;
	ld ady=a.second-fix.second;
	ld bdx=b.first-fix.first;
	ld bdy=b.second-fix.second;
	//1
	if(adx>=0&&ady>=0)
	{
		if(bdx==0&&bdy>0)
			return 1;
		if(bdx==0&&bdy<0)
			return 0;
		if(bdx>0&&bdy==0)
			return 0;
		if(bdx<0&&bdy==0)
			return 0;
		if(bdx>0&&bdy>0)
		{
			if(adx==0)
				return 0;
			if(ady==0)
				return 1;
			return (ld)ady/adx<(ld)bdy/bdx;//1
		}
		if(bdx<0&&bdy>0)
			return 1;
		else
			return 0;
	}
	//2
	if(adx<=0&&ady>=0)
	{
		if(bdx<0&&bdy>0)
			return (ld)ady/adx<(ld)bdy/bdx;//2
		else
			return 0;//1 3 4
	}
	//3
	if(adx<=0&&ady<=0)
	{
		if(ady==0&&adx<0)
			return 1;//1 2 4
		if(bdx<0&&bdy<0)
			return (ld)ady/adx<(ld)bdy/bdx;//3
		else
			return 1;//1 2 4
	}
	//4
	if(adx>=0&&ady<=0)
	{
		if(bdx==0&&bdy>0)
			return 1;
		if(bdx==0&&bdy<0)
			return 0;
		if(bdx>0&&bdy==0)
			return 1;
		if(bdx<0&&bdy==0)
			return 0;
		if(bdx>=0&&bdy<=0)
		{
			if(adx==0)
				return 1;
			if(ady==0)
				return 0;
			return (ld)ady/adx<(ld)bdy/bdx;
		}
		if(bdx<0&&bdy<0)
			return 0;
		else
			return 1;
	}
}

L.E.  A mers   O sa tin minte treaba asta. MS