Imprimă pagina - 1071 Hawaii

Titlul: 1071 Hawaii
Scris de: Marius Stroe din Iunie 18, 2010, 23:47:00

Aici puteţi discuta despre problema Hawaii (http://infoarena.ro/problema/hawaii).

Titlul: Răspuns: 1071 Hawaii
Scris de: Farcasanu Alexandru Ciprian din Iunie 19, 2010, 10:43:55

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

Titlul: Răspuns: 1071 Hawaii
Scris de: Cosmin Negruseri din Iunie 19, 2010, 11:22:57

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 :P

Titlul: Răspuns: 1071 Hawaii
Scris de: Tirca Bogdan din Iunie 21, 2010, 14:10:45

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

Titlul: Răspuns: 1071 Hawaii
Scris de: Andrei Parvu din Iunie 21, 2010, 15:35:44

Î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).

Titlul: Răspuns: 1071 Hawaii
Scris de: Tirca Bogdan din Iunie 21, 2010, 16:43:37

Frumos :D 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 :ok: O sa tin minte treaba asta. MS :yahoo:

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Marius Stroe din Iunie 18, 2010, 23:47:00