[Vari] Contest 8: Compattamento Barionico

[gugoXX]

Non so, non sto utilizzando alberi di ricerca (Mi e' sembrato di aver capito che li stai utilizzando).
Forse riesco a tagliare ancora qualcosa, ma ci pensero' con calma.

Si', per la ricerca del massimo sto utilizzando un po' di parallelismo, ma non sono molto soddisfatto della soluzione per ora.

[rеpne scasb]

■

[Vincenzo1968]

Ohé,

sto provando con quelli che Knuth(The Art of Computer Programming, Vol 3°, pag. 563) chiama post-office trees.

[Vincenzo1968]

Avrei bisogno di sapere come si fa a confrontare due punti.

Mi spiego:

data la seguente struttura:

typedef struct tagPunti
{
	double A;
	double B;
	double C;
} Punti;

Dovrei scrivere una funzione

int Compare(Punti a, Punti b) // Funzione di confronto

che mi restituisca -1 se il punto a è minore del punto b; 1 se a > b e 0 se a == b.

Come si implementa una funzione di confronto tra punti con coordinate tridimensionali?

Grazie

[^TiGeRShArK^]

Originariamente inviato da Vincenzo1968

Avrei bisogno di sapere come si fa a confrontare due punti.

Mi spiego:

data la seguente struttura:

typedef struct tagPunti
{
	double A;
	double B;
	double C;
} Punti;

Dovrei scrivere una funzione

int Compare(Punti a, Punti b) // Funzione di confronto

che mi restituisca -1 se il punto a è minore del punto b; 1 se a > b e 0 se a == b.

Come si implementa una funzione di confronto tra punti con coordinate tridimensionali?

Grazie

dovresti confrontare contemporaneamente le tre proiezioni sugli assi x, y, e z (che non sono altro che le coordinate del punto) credo....
EDIT:
e mi sa che devi anche stabilire una convenzione tua di ordinamento (per esempio assegnare una priorità diversa ai vari assi).
Solitamente si confrontano solo i moduli dei vettori definiti dai punti per ordinarli, per ordinare tutto il vettore devi stabilire tu se è + importante il modulo, o quale tra le due fasi....
O, come dicevo prima, un particolare asse...

[Vincenzo1968]

Originariamente inviato da ^TiGeRShArK^

dovresti confrontare contemporaneamente le tre proiezioni sugli assi x, y, e z (che non sono altro che le coordinate del punto) credo....

Grazie Tiger

per il momento sono riuscito ad ottenere questo:



I tempi sono buoni ma la funzione di confronto(evidentemente sbagliata) mi fa ottenere risultati errati

Non è che puoi postarmi uno pseudo codice?

[Tommo]

Uff... vorrei provare anche io, ma ho strani problemi di null pointers

Cmq volevo chiedere, a che serve usare un'albero di ricerca quando i dati sono ben conosciuti e puntiformi?

Non basta suddividere lo spazio in cellette messe in un array normale?

Cell* myCell = cells[ pos.x + side.x*pos.y + side.x*side.y*pos.z ];

Particle** nearParticles = myCell->getContainedParticles();
size_t nearParticlesNb = myCell->getContainedParticlesNb();

//confronta la distanza minima solo con le celle più vicine

Il vantaggio è che al crescere del numero di celle, trovare quella che contiene la particella costa esattamente uguale.
In più, mediamente le particelle in una cella sono un numero costante, quindi se celle/particelle si mantiene costante, il tutto pesa sempre uguale. Quasi.
Però: non funge nel caso che le due particelle più vicine siano a cavallo di due celle.

Ha senso?

[^TiGeRShArK^]

Originariamente inviato da Vincenzo1968

Grazie Tiger

per il momento sono riuscito ad ottenere queso:



I tempi sono buoni ma la funzione di confronto(evidentemente sbagliata) mi fa ottenere risultati errati

Non è che puoi postarmi uno pseudo codice?

eh beh..
non è che è errata la funzione di confronto è che non penso esista una funzione di confronto univocamente definita per dei vettori in uno spazio euclideo..
Tanto per farti un esempio se confronti semplicemente le tre coordinate senza dare una priorità come ti comporti nel caso in cui i due punti siano (1,5,2) e (2,3,1)?
la coordinata x è minore nel primo punto, ma la y e la z sono maggiori...
dunque se decidi che a parità di x vai a confrontare la y e quindi a parità di entrambi confronti la z puoi fare un ordinamento.
in pratica in pseudo-codice sarebbe qualcosa del genere:

def compare(p1, p2) {
    if (p1.x < p2.x || p1.y < p2.y || p1.z < p2.z)
        return -1
    else if (p1.x == p2.x && p1.y == p2.y && p1.z == p2.z)
        return 0
    else
        return 1

in questo modo tutti i punti in cui almeno una delle coordinate è minore della corrispettiva coordinata del punto da confrontare sono minori di esso, e sono maggiori se tutte e tre le coordinate sono maggiori.
Ma si deve vedere se a te va bene questo tipo di ordinamento o se ne devi utilizzare qualche altro..

[Vincenzo1968]

Posto il codice:

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <malloc.h>

#define BUFFER_SIZE 4096

int g_pass = 2;

//double distanzaMin = -1;
//double distanzaMax = -1;

typedef struct tagPunti
{
	int index;
	double A;
	double B;
	double C;
} Punti;

typedef struct tagRes
{
	Punti P1;
	Punti P2;
	double Distanza;
	int index1;
	int index2;
} Res;

typedef struct tagArray
{
	int dimensione;
	double dmax;
	Punti *m;
} Array;

typedef enum tagStati
{
	S_ERROR = -1, S0 = 0, S1, S2, S3, S4, S5, S6, S7, S8, S9
} Stati;


// La macro seguente restituisce il numero degli elementi di un array.
// Per esempio, data la seguente dichiarazione:
//
// int array[] = {8, 5, 13, 2, 1};
//
// ARRAY_SIZE(array) restituisce 5

#define ARRAY_SIZE(Array) (sizeof(Array) / sizeof((Array)[0]))

typedef Punti Item;
//typedef double Item;

int (*pfnCompare)(Item, Item) = NULL; // Puntatore alla funzione di confronto

int Compare(Item a, Item b) // Funzione di confronto
{
	// La funzione di confronto deve restituire un valore
	// minore di zero se a < b,
	// maggiore di zero se a > b
	// e zero se a e b sono uguali

	double x, y;

	if ( g_pass == 0 )
	{
		x = a.A;
		y = b.A;
		g_pass = 1;
	}
	else if ( g_pass == 1 )
	{
		x = a.B;
		y = b.B;
		g_pass = 2;
	}
	else if ( g_pass == 2 )
	{
		x = a.C;
		y = b.C;
		g_pass = 0;
	}

	if ( x < y )
		return -1;
	else if ( x > y )
		return 1;
	else
		return 0;
}

Stati DFA(const char *szFileName, Array *pArray)
{
	Stati stato = S0;
	FILE *fp;
	unsigned char buffer[BUFFER_SIZE];
	int numblocks;
	int numread;
	unsigned char c;
	int k, x, j;
	int riga, colonna;
	char szNum[256];
	double num;

	unsigned char byteCR = 0xD; // Carriage Return
	unsigned char byteLF = 0xA; // Line Feed

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	if ( fseek(fp, 0, SEEK_END) )
		return 0;

	numblocks = ftell(fp)/BUFFER_SIZE;
	if ( numblocks == 0 )
	{
		numblocks = 1;
	}
	else
	{
		if ( ftell(fp) % BUFFER_SIZE != 0 )
			numblocks++;
	}

	fseek(fp, 0, SEEK_SET);
	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 1 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}

	pArray->dimensione = 0;
	k = 0;
	c = *(buffer + k++);
	while ( 1 )
	{
		if ( c >= '0' && c <= '9' )
		{
			pArray->dimensione = pArray->dimensione * 10 + c - '0';
		}
		else if ( c == ' ' || c == '\t' )
		{
			j = 0;
			while ( c != byteLF )
			{
				c = *(buffer + k++);
				if ( c >= '0' && c <= '9' )
					szNum[j++] = c;
			}
			szNum[j] = '\0';
			pArray->dmax = atof(szNum);
			break;
		}
		else if ( c == '\n' )
		{
			break;
		}

		c = *(buffer + k++);
	}

	pArray->m = (Punti*)malloc(pArray->dimensione*sizeof(Punti));
	if ( !pArray->m )
	{
		printf("Memoria insufficiente.\n");
		fclose(fp);
		return S_ERROR;
	}

	riga = colonna = 0;
	num = 0;
	x = j = 0;
	while ( x < numblocks )
	{
		c = *(buffer + k++);

		if ( c == byteLF )
		{
			pArray->m[riga].index = riga;
			riga++;
			colonna = 0;
		}

		switch (stato)
		{
		case S0:
			j = 0;
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S2;
			}
			else if ( c == '.' )
			{
				szNum[j++] = c;
				stato = S3;
			}
			else if ( c == '-' || c == '+' )
			{
				szNum[j++] = c;
				stato = S1;
			}
			else if ( c == ' ' || c == '\t' )
			{
				while ( c == ' ' || c == '\t' )
				{
					c = *(buffer + k++);
					if ( k >= numread )
						break;
				}
				k--;
			}
			else if ( c == byteCR || c == byteLF )
			{
				// nada
			}
			else
			{
				printf("Errore: stato S0; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S1:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S2;
			}
			else if ( c == '.' )
			{
				szNum[j++] = c;
				stato = S3;
			}
			else
			{
				printf("Errore: stato S1; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S2:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
			}
			else if ( c == '.' )
			{
				szNum[j++] = c;
				stato = S4;
			}
			else if ( c == 'E' || c == 'e' )
			{
				szNum[j++] = c;
				stato = S5;
			}
			else if ( c == ' ' || c == '\t' || c == byteCR || c == byteLF )
			{
				szNum[j] = '\0';
				if ( colonna == 0 )
					pArray->m[riga].A = atof(szNum);
				else if ( colonna == 1 )
					pArray->m[riga].B = atof(szNum);
				else if ( colonna == 2 )
					pArray->m[riga].C = atof(szNum);
				colonna++;
				stato = S0;
			}
			else
			{
				printf("Errore: stato S2; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S3:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S6;
			}
			else
			{
				printf("Errore: stato S3; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S4:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S6;
			}
			else if ( c == 'E' || c == 'e' )
			{
				szNum[j++] = c;
				stato = S7;
			}
			else if ( c == ' ' || c == '\t' || c == byteCR || c == byteLF )
			{
				szNum[j] = '\0';
				if ( colonna == 0 )
					pArray->m[riga].A = atof(szNum);
				else if ( colonna == 1 )
					pArray->m[riga].B = atof(szNum);
				else if ( colonna == 2 )
					pArray->m[riga].C = atof(szNum);
				colonna++;
				stato = S0;
			}
			else
			{
				printf("Errore: stato S4; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S5:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S9;
			}
			else if ( c == '-' || c == '+' )
			{
				szNum[j++] = c;
				stato = S8;
			}
			else
			{
				printf("Errore: stato S5; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S6:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S6;
			}
			else if ( c == 'E' || c == 'e' )
			{
				szNum[j++] = c;
				stato = S7;
			}
			else if ( c == ' ' || c == '\t' || c == byteCR || c == byteLF )
			{
				szNum[j] = '\0';
				if ( colonna == 0 )
					pArray->m[riga].A = atof(szNum);
				else if ( colonna == 1 )
					pArray->m[riga].B = atof(szNum);
				else if ( colonna == 2 )
					pArray->m[riga].C = atof(szNum);
				colonna++;
				stato = S0;
			}
			else
			{
				printf("Errore: stato S6; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S7:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S9;
			}
			else if ( c == '-' || c == '+' )
			{
				szNum[j++] = c;
				stato = S8;
			}
			else
			{
				printf("Errore: stato S7; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;

		case S8:
		case S9:
			if ( c >= '0' && c <= '9' )
			{
				szNum[j++] = c;
				stato = S9;
			}
			else if ( c == ' ' || c == '\t' || c == byteCR || c == byteLF )
			{
				szNum[j] = '\0';
				if ( colonna == 0 )
					pArray->m[riga].A = atof(szNum);
				else if ( colonna == 1 )
					pArray->m[riga].B = atof(szNum);
				else if ( colonna == 2 )
					pArray->m[riga].C = atof(szNum);
				colonna++;
				stato = S0;
			}
			else
			{
				printf("Errore: stato S9; riga %d; colonna %d;\n", riga, colonna);
				fclose(fp);
				return S_ERROR;
			}
			break;
		}

		if ( k >= numread )
		{
			numread = fread(buffer, 1, BUFFER_SIZE, fp);
			k = 0;
			x++;
		}
	}

	fclose(fp);

	return stato;
}

void Calcola(Punti P[], int dim, Res *pMin, Res *pMax)
{
	int x;
	double distanza, distanzaMin, distanzaMax;
	double diffA, diffB, diffC;

	distanzaMin = distanzaMax = -1;

	for ( x = 1; x < dim; x++ )
	{
		diffA = P[x-1].A - P[x].A;
		diffB = P[x-1].B - P[x].B;
		diffC = P[x-1].C - P[x].C;
		distanza = diffA*diffA + diffB*diffB + diffC*diffC;
		if ( distanza < distanzaMin || distanzaMin == -1 )
		{
			distanzaMin = distanza;
			pMin->P1 = P[x-1];
			pMin->P2 = P[x];
			pMin->index1 = P[x-1].index;
			pMin->index2 = P[x].index;
		}
		if ( distanza > distanzaMax )
		{
			distanzaMax = distanza;
			pMax->P1 = P[x-1];
			pMax->P2 = P[x];
			pMax->index1 = P[x-1].index;
			pMax->index2 = P[x].index;
		}
	}

	pMin->Distanza = sqrt( distanzaMin );
	pMax->Distanza = sqrt( distanzaMax );
}

void QuickSortNonRecursive(Item *a, int start, int stop)
{
	int i, s = 0, stack[64];

	int up = start, down = stop - 1;
	Item part = a[stop];
	Item tmp;

	stack[s++] = start;
	stack[s++] = stop;

	while (s > 0)
	{
		stop = stack[--s];
		start = stack[--s];

		if (start >= stop)
			continue;

		//INIZIO PARTIZIONAMENTO

		up = start;
		down = stop - 1;
		part = a[stop];

		if (stop <= start)
		{
			i = start;
			continue;
		}

		while (1)
		{
			while ( (*pfnCompare)(a[up], part) < 0 )
				up++;

			while ( (*pfnCompare)(part, a[down]) < 0 && (up < down) )
				down--;

			if (up >= down)
				break;

			tmp = a[down];
			a[down] = a[up];
			a[up] = tmp;

			up++;
			down--;
		}

		tmp = a[stop];
		a[stop] = a[up];
		a[up] = tmp;

		i = up;

		// FINE PARTIZIONAMENTO

		if (i - start > stop - i)
		{
			stack[s++] = start;
			stack[s++] = i - 1;
			stack[s++] = i + 1;
			stack[s++] = stop;
		}
		else
		{
			stack[s++] = i + 1;
			stack[s++] = stop;
			stack[s++] = start;
			stack[s++] = i - 1;
		}
	}
}

int main()
{
	Stati stato;
	Array myArray;
	Res r1, r2;

	clock_t c_start, c_end;

	char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest 08 - Compattamento Barionico\\Coords\\Coords.dat";

	pfnCompare = Compare;

	c_start = clock();
	stato = DFA(szFileName, &myArray);
	c_end = clock();
	printf("\nTempo impiegato per caricamento dati -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	c_start = clock();
	QuickSortNonRecursive(myArray.m, 0, myArray.dimensione - 1);
	Calcola(myArray.m, myArray.dimensione, &r1, &r2);
	c_end = clock();

	printf("\nDistanza Min: P[%d] - P[%d] -> %.15lf\n", r1.index1, r1.index2, r1.Distanza);
	printf("\nDistanza Max: P[%d] - P[%d] -> %.15lf\n", r2.index1, r2.index2, r2.Distanza);
	printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	free(myArray.m);

	return 0;
}

Per ottenere risultati corretti bisogna modificare la funzione Compare

[Vincenzo1968]

Originariamente inviato da ^TiGeRShArK^

eh beh..
non è che è errata la funzione di confronto è che non penso esista una funzione di confronto univocamente definita per dei vettori in uno spazio euclideo..
Tanto per farti un esempio se confronti semplicemente le tre coordinate senza dare una priorità come ti comporti nel caso in cui i due punti siano (1,5,2) e (2,3,1)?
la coordinata x è minore nel primo punto, ma la y e la z sono maggiori...
dunque se decidi che a parità di x vai a confrontare la y e quindi a parità di entrambi confronti la z puoi fare un ordinamento.
in pratica in pseudo-codice sarebbe qualcosa del genere:

def compare(p1, p2) {
    if (p1.x < p2.x || p1.y < p2.y || p1.z < p2.z)
        return -1
    else if (p1.x == p2.x && p1.y == p2.y && p1.z == p2.z)
        return 0
    else
        return 1

in questo modo tutti i punti in cui almeno una delle coordinate è minore della corrispettiva coordinata del punto da confrontare sono minori di esso, e sono maggiori se tutte e tre le coordinate sono maggiori.
Ma si deve vedere se a te va bene questo tipo di ordinamento o se ne devi utilizzare qualche altro..

Io basavo il mio ragionamento sul caso unidimensionale.
Mi spiego: se ho un array non ordinato di double(che rappresenta un insieme di punti su una retta), per ricercare i due punti a distanza minima, debbo confrontare tutte le possibili coppie di punti(complessità = O(n^2).
Se invece ordino l'array, per trovare la coppia di punti a distanza minima mi basta scorrere l'array confrontando gli elementi adiacenti(complessità = O(n)).

Ho detto minchiate?

Se il ragionamento sul caso unidimensionale è corretto, è possibile applicarlo anche al caso tridimensionale?

[gugoXX]

Originariamente inviato da Vincenzo1968

Io basavo il mio ragionamento sul caso unidimensionale.
Mi spiego: se ho un array non ordinato di double(che rappresenta un insieme di punti su una retta), per ricercare i due punti a distanza minima, debbo confrontare tutte le possibili coppie di punti(complessità = O(n^2).
Se invece ordino l'array, per trovare la coppia di punti a distanza minima mi basta scorrere l'array confrontando gli elementi adiacenti(complessità = O(n)).

Ho detto minchiate?

Se il ragionamento sul caso unidimensionale è corretto, è possibile applicarlo anche al caso tridimensionale?

Purtroppo no, non e' applicabile neppure al caso bidimensionale.
Se la distanza PQ e' 5, e la distanza PR e' 6, non e' detto che QR sia solo 1.
Non sono neppure mantenute le distanze reciproche. Magari Q ed R distano tra loro piu' di quanto distavano da P (es: Triangolo ottusangolo)

Quindi non puoi ordinare i punti di un piano lungo una retta, pensando di calcolare le distanze reciproche solo ragionando sulla posizione del punto lungo la retta.
Occorre un'altra strategia.

[VICIUS]

Originariamente inviato da gugoXX

Purtroppo no, non e' applicabile neppure al caso bidimensionale.
Se la distanza PQ e' 5, e la distanza PR e' 6, non e' detto che QR sia solo 1.
Non sono neppure mantenute le distanze reciproche. Magari Q ed R distano tra loro piu' di quanto distavano da P (es: Triangolo ottusangolo)

Quindi non puoi ordinare i punti di un piano lungo una retta, pensando di calcolare le distanze reciproche solo ragionando sulla posizione del punto lungo la retta.
Occorre un'altra strategia.

Immagino sia dovuto alla perdita dell'ordinamento nel passaggio da R a C giusto?

[Vincenzo1968]

Originariamente inviato da gugoXX

Purtroppo no, non e' applicabile neppure al caso bidimensionale.
Se la distanza PQ e' 5, e la distanza PR e' 6, non e' detto che QR sia solo 1.
Non sono neppure mantenute le distanze reciproche. Magari Q ed R distano tra loro piu' di quanto distavano da P (es: Triangolo ottusangolo)

Quindi non puoi ordinare i punti di un piano lungo una retta, pensando di calcolare le distanze reciproche solo ragionando sulla posizione del punto lungo la retta.
Occorre un'altra strategia.

Ok, grazie mille

Mò provo con i kD-Trees e buona notte ai suonatori.

[^TiGeRShArK^]

Originariamente inviato da VICIUS

Immagino sia dovuto alla perdita dell'ordinamento nel passaggio da R a C giusto?

più che altro mi sa che R è isomorfo solo con una delle tre basi di R^3 che è il nostro spazio euclideo...
Quindi non è possibile stabilire un isomorfismo tra l'intero spazio vettoriale e il solo R e mi sa che così si perde l'ordinabilità assoluta.....
ma prendete con le pinze quello che ho detto che l'algebra lineare mi è sempre stata sulle bolls..

[gugoXX]

Originariamente inviato da VICIUS

Immagino sia dovuto alla perdita dell'ordinamento nel passaggio da R a C giusto?

Diciamo che e' simile al passaggio da C ad R.
Non puoi trovare una relazione d'ordine tra i numeri complessi, cosi' come non la puoi trovare tra i punti del piano.

Non puoi dire che il punto P sia maggiore del punto Q o viceversa.

PS: Ho pensato un algoritmo greedy* che dovrebbe essere decisamente veloce. Stasera lo posto

greedy*: Algoritmo tipicamente molto veloce (o semplice) che riesce a trovare una soluzione soddisfacente ma che non e' detto che sia la soluzione ottima.
http://it.wikipedia.org/wiki/Algoritmo_greedy

Un algoritmo greedy è un algoritmo che cerca di ottenere una soluzione ottima da un punto di vista globale attraverso la scelta della soluzione più golosa (aggressiva o avida, a seconda della traduzione preferita del termine greedy dall'inglese) ad ogni passo locale. Questa tecnica consente, dove applicabile (infatti non sempre si arriva ad una soluzione ottima), di trovare soluzioni ottimali per determinati problemi in un tempo polinomiale (cfr. Problemi NP-Completi, cioè problemi di soluzione non deterministica polinomiale).

Vedremo il risultato.

[marco.r]

Uhm, contest poco utile secondo me perche' c'e' sia un sacco di teoria che di codice gia' fatto per trovare i punti piu' vicini.
Comunque, visto che il bello dei contest e' che servono a poco e ci si diverte un sacco, posto anche io una mia soluzione custom, per il momento per la coppia piu' lontana.

#include <iostream>
#include <vector>
#include <fstream>
#include <set>
#include <iterator>
#include <cmath>
#include <algorithm>

using std::cout;
using std::endl;
using std::make_pair;
using std::set;
using std::pair;

struct point
{
    point(){}
    point(double _x, double _y, double _z ):x(_x),y(_y),z(_z){}
    double x,y,z;
};

std::vector<point> data;
std::set<int> feasible_set;
point corners[8];

double max_distance = 0.0;
std::pair<int,int> max_pair;
double size;
int dim;



std::istream& operator >> (std::istream& in, point& p )
{
    in >> p.x >> p.y >> p.z;
    return in;
}

std::ostream& operator << (std::ostream& out, point& p )
{
    out << p.x << ' ' << p.y << ' ' << p.z;
    return out;
}


double distance(const point& p1, const point& p2 )
{
    double dx,dy,dz;
    dx = p1.x - p2.x;
    dy = p1.y - p2.y;
    dz = p1.z - p2.z;
    return dx*dx + dy*dy + dz*dz;
}

pair<int,double> most_distant(const point& p)
{
    double dist = 0;
    int idx = -1;
    for ( std::set<int>::const_iterator i = feasible_set.begin();
          i != feasible_set.end();
          ++i )
    {
        double d = distance(p,data[*i]);
        if ( d > dist )
        {
            dist = d;
            idx = *i;
        }
    }
    return make_pair(idx,dist);
}

bool feasible( const point& p )
{
    for ( int i=0 ; i<8 ; ++i )
    {
        if ( distance(p,corners[i]) > max_distance )
            return true;
    }
    return false;

}

       
void init( double size )
{
    corners[0] = point( 0, 0, 0 );
    corners[1] = point( 0, 0, 1 );
    corners[2] = point( 0, 1, 0 );
    corners[3] = point( 0, 1, 1 );
    corners[4] = point( 1, 0, 0 );
    corners[5] = point( 1, 0, 1 );
    corners[6] = point( 1, 1, 0 );
    corners[7] = point( 1, 1, 1 );

}

bool unfeasible( const int& x )
{
    return !feasible(data[x]);
}


void remove_unfeasible()
{
    for ( set<int>::const_iterator i = feasible_set.begin();
          i != feasible_set.end();
          ++i )
    {
        if ( unfeasible(*i) )
        {
            feasible_set.erase( i );
        }
    }
}

void update_feasible_set( const point& p, int index )
{
    if ( feasible(p) )
    {
        pair<int,double> x = most_distant(p);
        const int& idx = x.first;
        const double& d = x.second;
        if ( d > max_distance )
        {
            max_distance = d;
            max_pair = std::make_pair( index, idx );
        }

        remove_unfeasible();
        feasible_set.insert(index);
    }
}

void solve_max()
{
    std::cout << "Looking for greatest distance" << std::endl;
    feasible_set.insert( 0 );
    feasible_set.insert( 1 );
    max_distance = distance( data[0], data[1] );
    max_pair = make_pair(0,1);
    for ( int i=2 ; i<data.size() ; ++i )
    {
        update_feasible_set( data[i], i );
    }
    cout << "Max distance is " << sqrt(max_distance) << " [" << max_pair.first << ',' << max_pair.second << "]" << endl;
    cout << data[max_pair.first] << endl;
    cout << data[max_pair.second] << endl;
}

int main(int argc, char** argv)
{
    const char* filename = argc > 1 ? argv[1] : "Coords.dat";
    
    std::ifstream input(filename);
    std::cout << "Reading data set ... " << std::endl;
    input >> dim >> size;
    init(size);
    
    data.resize(dim);
    std::copy( std::istream_iterator<point>(input),
               std::istream_iterator<point>(),
               data.begin() );
    
    solve_max();

}

L'idea di base e' che i punti piu' distanti staranno al'langolo del cubo. Per cui an mano che scorro i punti letti elimino quelli che non possono contribuire alla soluzione finale perche' troppo in centro (ovvero distano dall'angolo del cubo piu' lontano meno della soluzione corrente migliore).
Non pensavo, ma anche con diverse centinaia di migliaia di valori, riesco a tenere il working set sotto la cinquantina di elementi, per cui anche un confronto "brute force" con questi risulta sufficiente.
Ho una idea custom anche per l'altro problema, stasera che avro' tempo spero di svilupparla un attimo.

[marco.r]

ops,
ovviamente c'e' un errore nella init , irrilevante per il dataset attuale cmq (che sta nel cubo unitario)

[Vincenzo1968]

Originariamente inviato da gugoXX

...
PS: Ho pensato un algoritmo greedy* che dovrebbe essere decisamente veloce. Stasera lo posto

greedy*: Algoritmo tipicamente molto veloce (o semplice) che riesce a trovare una soluzione soddisfacente ma che non e' detto che sia la soluzione ottima.
http://it.wikipedia.org/wiki/Algoritmo_greedy

Vedremo il risultato.

Io ce l'ho un algoritmo greedy ma non è molto veloce(ci vogliono due giorni):

Tratto da Gli arancini di Montalbano di Andrea Camilleri:

Adelina ci metteva due jornate sane sane a pripararli. Ne sapeva, a memoria, la ricetta. Il giorno avanti si fa un aggrassato di vitellone e di maiale in parti uguali che deve còciri a foco lentissimo per ore e ore con cipolla, pummadoro, sedano, prezzemolo e basilico. Il giorno appresso si pripara un risotto, quello che chiamano alla milanisa(senza zaffirano, pi carità!), lo si versa sopra a una tavola, ci si impastano le ova e lo si fa rifriddare. Intanto si còcino i pisellini, si fa una besciamella, si riducono a pezzettini 'na poco di fette di salame e si fa tutta una composta con la carne aggrassata, triturata a mano con la mezzaluna(nenti frullatore, pi carità di Dio!). Il suco della carne s'ammisca col risotto. A questo punto si piglia tanticchia di risotto, s'assistema nel palmo d'una mano fatta a conca, ci si mette dentro quanto un cucchiaio di composta e si copre con dell'altro riso a formare una bella palla. Ogni palla la si fa rotolare nella farina, poi si passa nel bianco d'ovo e nel pane grattato. Doppo, tutti gli arancini s'infilano in una paredda d'oglio bollente e si fanno friggere fino a quando pigliano un colore d'oro vecchio. Si lasciano scolare sulla carta. E alla fine, ringraziannu u Signuruzzu, si mangiano!

[^TiGeRShArK^]

Originariamente inviato da marco.r

Uhm, contest poco utile secondo me perche' c'e' sia un sacco di teoria che di codice gia' fatto per trovare i punti piu' vicini.
Comunque, visto che il bello dei contest e' che servono a poco e ci si diverte un sacco, posto anche io una mia soluzione custom, per il momento per la coppia piu' lontana.

#include <iostream>
#include <vector>
#include <fstream>
#include <set>
#include <iterator>
#include <cmath>
#include <algorithm>

using std::cout;
using std::endl;
using std::make_pair;
using std::set;
using std::pair;

struct point
{
    point(){}
    point(double _x, double _y, double _z ):x(_x),y(_y),z(_z){}
    double x,y,z;
};

std::vector<point> data;
std::set<int> feasible_set;
point corners[8];

double max_distance = 0.0;
std::pair<int,int> max_pair;
double size;
int dim;



std::istream& operator >> (std::istream& in, point& p )
{
    in >> p.x >> p.y >> p.z;
    return in;
}

std::ostream& operator << (std::ostream& out, point& p )
{
    out << p.x << ' ' << p.y << ' ' << p.z;
    return out;
}


double distance(const point& p1, const point& p2 )
{
    double dx,dy,dz;
    dx = p1.x - p2.x;
    dy = p1.y - p2.y;
    dz = p1.z - p2.z;
    return dx*dx + dy*dy + dz*dz;
}

pair<int,double> most_distant(const point& p)
{
    double dist = 0;
    int idx = -1;
    for ( std::set<int>::const_iterator i = feasible_set.begin();
          i != feasible_set.end();
          ++i )
    {
        double d = distance(p,data[*i]);
        if ( d > dist )
        {
            dist = d;
            idx = *i;
        }
    }
    return make_pair(idx,dist);
}

bool feasible( const point& p )
{
    for ( int i=0 ; i<8 ; ++i )
    {
        if ( distance(p,corners[i]) > max_distance )
            return true;
    }
    return false;

}

       
void init( double size )
{
    corners[0] = point( 0, 0, 0 );
    corners[1] = point( 0, 0, 1 );
    corners[2] = point( 0, 1, 0 );
    corners[3] = point( 0, 1, 1 );
    corners[4] = point( 1, 0, 0 );
    corners[5] = point( 1, 0, 1 );
    corners[6] = point( 1, 1, 0 );
    corners[7] = point( 1, 1, 1 );

}

bool unfeasible( const int& x )
{
    return !feasible(data[x]);
}


void remove_unfeasible()
{
    for ( set<int>::const_iterator i = feasible_set.begin();
          i != feasible_set.end();
          ++i )
    {
        if ( unfeasible(*i) )
        {
            feasible_set.erase( i );
        }
    }
}

void update_feasible_set( const point& p, int index )
{
    if ( feasible(p) )
    {
        pair<int,double> x = most_distant(p);
        const int& idx = x.first;
        const double& d = x.second;
        if ( d > max_distance )
        {
            max_distance = d;
            max_pair = std::make_pair( index, idx );
        }

        remove_unfeasible();
        feasible_set.insert(index);
    }
}

void solve_max()
{
    std::cout << "Looking for greatest distance" << std::endl;
    feasible_set.insert( 0 );
    feasible_set.insert( 1 );
    max_distance = distance( data[0], data[1] );
    max_pair = make_pair(0,1);
    for ( int i=2 ; i<data.size() ; ++i )
    {
        update_feasible_set( data[i], i );
    }
    cout << "Max distance is " << sqrt(max_distance) << " [" << max_pair.first << ',' << max_pair.second << "]" << endl;
    cout << data[max_pair.first] << endl;
    cout << data[max_pair.second] << endl;
}

int main(int argc, char** argv)
{
    const char* filename = argc > 1 ? argv[1] : "Coords.dat";
    
    std::ifstream input(filename);
    std::cout << "Reading data set ... " << std::endl;
    input >> dim >> size;
    init(size);
    
    data.resize(dim);
    std::copy( std::istream_iterator<point>(input),
               std::istream_iterator<point>(),
               data.begin() );
    
    solve_max();

}

L'idea di base e' che i punti piu' distanti staranno al'langolo del cubo. Per cui an mano che scorro i punti letti elimino quelli che non possono contribuire alla soluzione finale perche' troppo in centro (ovvero distano dall'angolo del cubo piu' lontano meno della soluzione corrente migliore).
Non pensavo, ma anche con diverse centinaia di migliaia di valori, riesco a tenere il working set sotto la cinquantina di elementi, per cui anche un confronto "brute force" con questi risulta sufficiente.
Ho una idea custom anche per l'altro problema, stasera che avro' tempo spero di svilupparla un attimo.

ecco, bravo...
hai scritto quello su cui stavo lavorando io
io però lo stavo facendo con le coordinate sferiche

[VICIUS]

Originariamente inviato da ^TiGeRShArK^

più che altro mi sa che R è isomorfo solo con una delle tre basi di R^3 che è il nostro spazio euclideo [...]

Originariamente inviato da gugoXX

Diciamo che e' simile al passaggio da C ad R.
Non puoi trovare una relazione d'ordine tra i numeri complessi, cosi' come non la puoi trovare tra i punti del piano. [...]

Capito. Vado a rileggermi gli appunti di algebra 1... se li trovo ancora