[Vari] Contest 8: Compattamento Barionico

[^TiGeRShArK^]

Originariamente inviato da Vincenzo1968

Vedi com'è divertente? Il dialetto romanesco non è poi così difficile da capire(grazie anche all'uso che se ne fa in letteratura e, soprattutto, nel cinema)

io più che altro sono stato poco + di un anno a lavorare a roma e con i miei colleghi ormai m'ero abituato

[gugoXX]

Ecco, ecco...

public class Universe
{
    public List<Point3d> Allpoints;

    public Universe()
    {
        Allpoints = new List<Point3d>();
    }

    public void Load(string fname)
    {
        StreamReader sr = new StreamReader(fname);
        string stt = sr.ReadLine();
        string[] first = stt.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
        int howmany = int.Parse(first[0]);
        LatoCubo = double.Parse(first[1]);
        string line;
        while ((line = sr.ReadLine()) != null)
        {
            string[] coords = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            Allpoints.Add(new Point3d(double.Parse(coords[0]),double.Parse(coords[1]),double.Parse(coords[2])));
        }
        sr.Close();
    }

    public void Save(string fname)
    {
        StreamWriter sw = new StreamWriter(fname);
        sw.WriteLine("{0} {1}", Allpoints.Count, LatoCubo);
        foreach (Point3d p3d in Allpoints)
        {
            sw.WriteLine(p3d.ToString());
        }
        sw.Close();
    }

    public double LatoCubo;
    public void Generate(int npoints,double dim)
    {
        LatoCubo = dim;
        Allpoints.Clear();
        for (int t = 0; t < npoints; t++)
        {
            Allpoints.Add(Point3d.Rand(dim));
        }
    }                                
}

[Vincenzo1968]

Originariamente inviato da gugoXX

Ecco, ecco...

public class Universe
{
    public List<Point3d> Allpoints;

    public Universe()
    {
        Allpoints = new List<Point3d>();
    }

    public void Load(string fname)
    {
        StreamReader sr = new StreamReader(fname);
        string stt = sr.ReadLine();
        string[] first = stt.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
        int howmany = int.Parse(first[0]);
        LatoCubo = double.Parse(first[1]);
        string line;
        while ((line = sr.ReadLine()) != null)
        {
            string[] coords = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            Allpoints.Add(new Point3d(double.Parse(coords[0]),double.Parse(coords[1]),double.Parse(coords[2])));
        }
        sr.Close();
    }

    public void Save(string fname)
    {
        StreamWriter sw = new StreamWriter(fname);
        sw.WriteLine("{0} {1}", Allpoints.Count, LatoCubo);
        foreach (Point3d p3d in Allpoints)
        {
            sw.WriteLine(p3d.ToString());
        }
        sw.Close();
    }

    public double LatoCubo;
    public void Generate(int npoints,double dim)
    {
        LatoCubo = dim;
        Allpoints.Clear();
        for (int t = 0; t < npoints; t++)
        {
            Allpoints.Add(Point3d.Rand(dim));
        }
    }                                
}

Me dà erore: indice oltre i limiti della matrice.

[gugoXX]

Originariamente inviato da Vincenzo1968

Me dà erore: indice oltre i limiti della matrice.

Dove? Il file di input e' secondo specifiche?

[Vincenzo1968]

Originariamente inviato da gugoXX

Dove? Il file di input e' secondo specifiche?

Ho provato sia col file tuo(quello da 100.000 punti )che con quello di repne(file da 1.000.000 di punti).
A runtime ho quell'errore. Te posso posta' er screenshotte.

[Vincenzo1968]

Eqque qua:

[Vincenzo1968]

In omaggio al dialetto romanesco, ecco una poesia di Trilussa(e ringrazio Gugo per avermela segnalata):

LA POESIA DELL'UCELLETTO

Era d’Agosto e un povero uccelletto
ferito dallo fionda di un maschietto
andò per riposare l’ala offesa,
sulla finestra aperta di una chiesa.
Dalle tendine del confessionale
il parroco intravide l’animale
ma, pressato dal ministero urgente,
rimase intento a confessar la gente.
Mentre in ginocchio alcuni altri a sedere
dicevano i fedeli le preghiere,
una donna, notato l’uccelletto,
lo prese al caldo e se lo mise al petto.
D'un tratto un cinguettio ruppe il silenzio
e il prete a quel rumore
il ruolo abbandonò di confessore.
Scuro in viso peggio della pece,
s'arrampicò sul pulpito e poi fece:
“Fratelli! Chi ha l’uccello per favore
esca fuori dal tempio del Signore!”
I maschi, un po’ stupiti a tal parole,
lenti s'accinsero ad alzar le suole,
ma il prete a quell'errore madornale
“Fermi” gridò “mi sono espresso male!
Rientrate tutti e statemi a sentire,
solo chi ha preso l’uccello deve uscire!”
A testa bassa, la corona in mano,
cento donne s'alzarono pian piano.
Ma mentre se ne andavano ecco allora che il parroco strillò:
“Sbagliate ancora, rientrate tutte quante figlie amate
che in non volevo dir quel che pensate!
Ecco, quello che ho detto torno a dire,
solo chi ha preso l'uccello deve uscire,
ma, mi rivolgo, non ci sia sorpresa,
soltanto a chi l'uccello l’ha preso in chiesa!”
Finì la frase e nello stesso istante
le monache s'alzarono tutte quante
e con il volto pieno di rossore
lasciavano la casa del Signore.
“O Santa Vergine!” esclamo il buon prete
“Fatemi la grazia se potete.
Poi senza fare rumore dico, piano piano
s'alzi soltanto chi ha l’uccello in mano!”
Una ragazza che col fidanzato s'era messa in un angolo appartato
sommessa mormorò con viso smorto
“Che ti dicevo, hai visto? Se n’è accorto!”

Qui è recitata da Andrea Bocelli:

http://it.youtube.com/watch?v=sYB7Ev5yLR0

[Vincenzo1968]

Ho risolto il problema anche per la ricerca della distanza massima. Adesso il risultato è corretto ma l'algoritmo è lento; impiega più di trenta secondi sul file grosso(quello postato da repne, da un milone di record).

Per la ricerca della distanza minima, invece, i tempi risultano, incredibilmente, più veloci di quelli di repne

File da 100.000 records:


File da 1.000.000 di records:


La mia macchina:

AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional (32 bit)
Service Pack 3

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

#define BUFFER_SIZE 4096
#define MAX_STACK 100

typedef double ElementType;
typedef ElementType ItemType[3];

typedef struct tagPunti
{
	ItemType data;
	int index;
} 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 struct tagTree
{
	Punti P;
	//struct tagTree *father;
	struct tagTree *left;
	struct tagTree *right;
} Tree;

Tree *NewNode(ItemType key, int index);
Tree *InsertNode(Tree *node, ItemType key, int index);
void FreeTree(Tree *head);


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]))

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';
				pArray->m[riga].data[colonna++] = atof(szNum);
				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';
				pArray->m[riga].data[colonna++] = atof(szNum);
				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';
				pArray->m[riga].data[colonna++] = atof(szNum);
				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';
				pArray->m[riga].data[colonna++] = atof(szNum);
				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;
}

Tree *NewNode(ItemType key, int index)
{
	Tree *r;

	r = (Tree *) malloc(sizeof(Tree));

	if(!r)
	{
		printf("Memoria insufficiente.\n");
		return NULL;
	}

	r->P.data[0] = key[0];
	r->P.data[1] = key[1];
	r->P.data[2] = key[2];
	r->P.index = index;
	//r->father = NULL;
	r->left = NULL;
	r->right = NULL;

	return r;
}

Tree *InsertNode(Tree *node, ItemType key, int index)
{
	Tree *pRadice = NULL;
	int Level = 0;

	if( !node )
	{
		node = NewNode(key, index);
		return node;
	}

	pRadice = node;
	
	while( 1 )
	{
		if ( key[Level] < node->P.data[Level] )
		{
			if ( !node->left )
			{
				node->left = NewNode(key, index);
				//node->left->father = node;
				break;
			}
			node = node->left;
		}
		else
		{
			if ( !node->right )
			{
				node->right = NewNode(key, index);
				//node->right->father = node;
				break;
			}
			node = node->right;
		}
		Level++;
		if ( Level > 2 )
			Level = 0;
	}

	node = pRadice;

	return node;
}

void FreeTree(Tree *head)
{
	Tree *temp1, *temp2;

	Tree *stack[MAX_STACK];
	int top;

	top = 0;
 
	if ( !head )
		return;

	temp1 = temp2 = head;

	while ( temp1 != NULL )
	{
		for(; temp1->left != NULL; temp1 = temp1->left)
			stack[top++] = temp1;

		while ( (temp1 != NULL) && (temp1->right == NULL || temp1->right == temp2) )
		{
			temp2 = temp1;
			free(temp2);
			if ( top == 0 )
				return;
			temp1 = stack[--top];
		}

		stack[top++] = temp1;
		temp1 = temp1->right;
	}
}

void TreeToArrayMin(Tree *head, Array *pArray)
{
	Tree *temp;

	Tree *stack[MAX_STACK];
	int top = 0;
	int k = 0;

	if ( !head )
		return;

	temp = head;

	stack[top++] = temp; // Push

	while ( top != 0 )
	{
		temp = stack[--top]; // Pop

		//printf("%d -> (%lf,%lf,%lf)\n", temp->index, temp->data[0], temp->data[1], temp->data[2]);			
		pArray->m[k++] = temp->P;

		if ( temp->right != NULL )
			stack[top++] = temp->right;
		if ( temp->left != NULL )
			stack[top++] = temp->left;
	} 
}

void MakeArrayMax(Array *pArray, Array *pArrayMax1, Array *pArrayMax2)
{
	int k, j, x;
	double decimo;
	double distanza;
	double diffA, diffB, diffC;
	double range1, range2;

	decimo = pArray->dmax / 15.0;
	range1 = pArray->dmax - decimo;
	range2 = pArray->dmax*2.0 - decimo;

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

	pArrayMax2->m = (Punti*)malloc(pArray->dimensione/2*sizeof(Punti));
	if ( !pArrayMax2->m )
	{
		printf("Memoria insufficiente.\n");
		free(pArrayMax1->m);
		return;
	}

	j = x = 0;
	for ( k = 0; k < pArray->dimensione; k++ )
	{
		diffA = pArray->m[k].data[0];
		diffB = pArray->m[k].data[1];
		diffC = pArray->m[k].data[2];
		distanza = diffA*diffA + diffB*diffB + diffC*diffC;

		if ( (distanza > range1) && (distanza < pArray->dmax) )
		{
			pArrayMax1->m[j++] = pArray->m[k];
			/*
			if ( pArray->m[k].index == 48483 )
			{
				printf("Eccolo -> 48483\n");
			}
			*/
		}
		else if ( distanza > range2 )
		{
			pArrayMax2->m[x++] = pArray->m[k];
			/*
			if ( pArray->m[k].index == 72832 )
			{
				printf("Eccolo -> 72832\n");
			}
			*/
		}

	}

	pArrayMax1->dimensione = j;
	pArrayMax1->dmax = pArray->dmax;

	pArrayMax2->dimensione = x;
	pArrayMax2->dmax = pArray->dmax;
}

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

	distanzaMin = -1;

	for ( x = 1; x < dim; x++ )
	{		
		diffA = P[x-1].data[0] - P[x].data[0];
		diffB = P[x-1].data[1] - P[x].data[1];
		diffC = P[x-1].data[2] - P[x].data[2];
		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;
		}
	}

	pMin->Distanza = sqrt( distanzaMin );
}

void CalcolaMax(Punti P1[], Punti P2[], int dim1, int dim2, Res *pMax)
{
	int x, y;
	double distanza, distanzaMax;
	double diffA, diffB, diffC;

	distanzaMax = -1;

	x = y = 0;

	while( x < dim1 )
	{
		//y = x + 1;
		y = 0;
		while( y < dim2 )
		{
			//distanza = sqrt( pow(P[x].A - P[y].A, 2.0) + pow(P[x].B - P[y].B, 2.0) + pow(P[x].C - P[y].C, 2.0) );
			diffA = P1[x].data[0] - P2[y].data[0];
			diffB = P1[x].data[1] - P2[y].data[1];
			diffC = P1[x].data[2] - P2[y].data[2];
			distanza = diffA*diffA + diffB*diffB + diffC*diffC;

			if ( distanza > distanzaMax )
			{
				distanzaMax = distanza;
				pMax->P1 = P1[x];
				pMax->P2 = P2[y];
				pMax->index1 = P1[x].index;
				pMax->index2 = P2[y].index;
			}
			++y;
		}
		++x;
	}

	pMax->Distanza = sqrt( distanzaMax );
}

int main()
{
	Stati stato;
	Array myArray, myArrayMax1, myArrayMax2;
	Res r1, r2;
	Tree *pTree = NULL;
	int k;
	double t1, t2;

	clock_t c_start, c_end;

	//char *szFileName = "C:\\Temp\\Coords\\Coords.dat";
	char *szFileName = "C:\\Temp\\Coords2\\Coords.dat";

	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();
	MakeArrayMax(&myArray, &myArrayMax1, &myArrayMax2);
	for(k = 0; k < myArray.dimensione; k++)
		pTree = InsertNode(pTree, myArray.m[k].data, myArray.m[k].index);
	TreeToArrayMin(pTree, &myArray);
	CalcolaMin(myArray.m, myArray.dimensione, &r1);
	c_end = clock();
	t1 = (double)(c_end - c_start) / CLOCKS_PER_SEC;

	c_start = clock();
	CalcolaMax(myArrayMax1.m, myArrayMax2.m, myArrayMax1.dimensione, myArrayMax2.dimensione, &r2);
	c_end = clock();
	t2 = (double)(c_end - c_start) / CLOCKS_PER_SEC;

	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 della distanza minima -> %5.5f secondi\n", t1);
	printf("\nTempo impiegato per la ricerca della distanza massima -> %5.5f secondi\n", t2);

	free(myArray.m);
	free(myArrayMax1.m);
	free(myArrayMax2.m);
	FreeTree(pTree);

	return 0;
}

Volevo postare una classifica, ma:

La soluzione di Gugo mi dà questi errori a runtime:


La soluzione di Marco.r, invece, va in crash.

[gugoXX]

Rimetto qui il codice, ma dovrebbe essere uguale a prima

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Diagnostics;

namespace Project6b
{
    public static class MainClass
    {
        static void Main(string[] args)
        {
            Universe dc = new Universe();
            dc.Load(@"C:\temp\Coords.dat");
            Stopwatch sw = new Stopwatch();
            sw.Start();
            ResearchMin clus = new ResearchMin(dc.Allpoints, dc.LatoCubo);
            var resmin = clus.Research();
            long mintime = sw.ElapsedMilliseconds;
            ResearchMax2 rmax = new ResearchMax2(dc.Allpoints, dc.LatoCubo);
            var resmax = rmax.Research();

            sw.Stop();
            Console.WriteLine("ResMin : {0}ms  {1}", mintime, resmin);
            Console.WriteLine("ResMax : {0}ms  {1}", sw.ElapsedMilliseconds - mintime, resmax);
            Console.WriteLine("{0}ms", sw.ElapsedMilliseconds);
            Console.ReadKey();
        }
    }


    public class Point3d
    {
        public double x;
        public double y;
        public double z;
        public Point3d(double ix, double iy, double iz)
        {
            x = ix;
            y = iy;
            z = iz;
        }

        public static Random rnd = new Random(18);
        public static Point3d Rand(double dim)
        {
            return new Point3d(rnd.NextDouble() * dim, rnd.NextDouble() * dim, rnd.NextDouble() * dim);
        }

        public static double operator -(Point3d d1, Point3d d2)
        {
            double dx = d2.x - d1.x;
            double dy = d2.y - d1.y;
            double dz = d2.z - d1.z;
            return (dx * dx + dy * dy + dz * dz);
        }

        public override string ToString()
        {
            return string.Format("{0} {1} {2}", x, y, z);
        }
    }


    public class Result
    {
        public Result(double init)
        {
            dis = init;
        }

        public Result(double p_dis, int i1, int i2)
        {
            dis = p_dis;
            index1 = i1;
            index2 = i2;
        }

        public double dis;
        public int index1, index2;

        public override string ToString()
        {
            return string.Format("Dist: {0} Indexes: {1}-{2}", Math.Sqrt(dis), index1, index2);
        }

        public static Result Greatest(Result r1, Result r2)
        {
            if (r1.dis > r2.dis) return r1;
            return r2;
        }
    }

    public class Point3dIndex : Point3d
    {
        public Point3dIndex(double x, double y, double z, int Idx)
            : base(x, y, z)
        {
            Index = Idx;
        }

        public int Index;

    }

    public class ResearchMin
    {
        List<Point3d> allpoints;
        int SplitFactor;
        double LatoCubo;

        public ResearchMin(List<Point3d> input, double LCubo)
        {
            allpoints = input;
            LatoCubo = LCubo;
        }

        List<Point3dIndex>[, ,] Zoner;

        public Result Research()
        {
            int ln = allpoints.Count;
            if (ln == 1)
            {
                return new Result(0, 0, 0);
            }
            if (ln == 2)
            {
                double dis = allpoints[1] - allpoints[2];
                Result rr = new Result(dis, 0, 1);
            }

            Result res = new Result(double.MaxValue);
            double SplitFactorD = (int)(2 * Math.Sqrt(Math.Sqrt(allpoints.Count)));
            int SplitFactor = (int)SplitFactorD;

            RsMin(SplitFactor, res, false);
            RsMin(SplitFactor, res, true);

            if (res.dis > (LatoCubo / SplitFactorD))
                throw new Exception("Minicubi troppo piccoli (Pochi punti, soluzione classica)");

            return res;
        }

        private Result RsMin(int sp, Result res, bool Sfasa)
        {
            SplitFactor = sp;

            double DimCella = LatoCubo / (double)SplitFactor;

            // Initialize Cluster
            int SpFSf = SplitFactor + (Sfasa ? 1 : 0);
            Zoner = new List<Point3dIndex>[SpFSf, SpFSf, SpFSf];
            for (int x = 0; x < SpFSf; x++)
            {
                for (int y = 0; y < SpFSf; y++)
                {
                    for (int z = 0; z < SpFSf; z++)
                    {
                        Zoner[x, y, z] = new List<Point3dIndex>();
                    }
                }
            }

            double sfasa = (Sfasa) ? (DimCella / 2) : 0;
            // Clusterize
            int ln = allpoints.Count;
            for (int t = 0; t < ln; t++)
            {
                Point3d p3d = allpoints[t];
                Point3dIndex p3di = new Point3dIndex(p3d.x, p3d.y, p3d.z, t);

                int nx = Normalize(p3d.x + sfasa, LatoCubo, SplitFactor);
                int ny = Normalize(p3d.y + sfasa, LatoCubo, SplitFactor);
                int nz = Normalize(p3d.z + sfasa, LatoCubo, SplitFactor);

                Zoner[nx, ny, nz].Add(p3di);
            }

            for (int x = 0; x < SpFSf; x++)
            {
                for (int y = 0; y < SpFSf; y++)
                {
                    for (int z = 0; z < SpFSf; z++)
                    {
                        MinWithinList1(Zoner[x, y, z], res);
                    }
                }
            }

            return res;
        }

        private void MinWithinList1(List<Point3dIndex> src, Result CurrentResult)
        {
            int ln = src.Count;
            for (int t = 0; t < ln - 1; t++)
            {
                Point3dIndex p3di1 = src[t];
                for (int u = t + 1; u < ln; u++)
                {
                    Point3dIndex p3di2 = src[u];
                    double dist = p3di2 - p3di1;

                    if (dist < CurrentResult.dis)
                    {
                        CurrentResult.dis = dist;
                        CurrentResult.index1 = p3di1.Index;
                        CurrentResult.index2 = p3di2.Index;
                    }
                }
            }
        }

        private int Normalize(double val, double max, int SplitFactor)
        {
            return (int)((val / max) * (double)SplitFactor);
        }
    }

    public class ResearchMax2
    {
        private class rm2
        {
            public rm2(Point3d rif)
            {
                riferimento = rif;
            }
            public Point3dIndex punto;
            public Point3d riferimento;
            public double cdist = double.MaxValue;
        }

        List<Point3d> allpoints;
        double LatoCubo;

        public ResearchMax2(List<Point3d> ap, double lc)
        {
            allpoints = ap;
            LatoCubo = lc;
        }

        rm2 cmmm = new rm2(new Point3d(0, 0, 0));
        rm2 cmmp = new rm2(new Point3d(0, 0, 1));
        rm2 cmpm = new rm2(new Point3d(0, 1, 0));
        rm2 cmpp = new rm2(new Point3d(0, 1, 1));
        rm2 cpmm = new rm2(new Point3d(1, 0, 0));
        rm2 cpmp = new rm2(new Point3d(1, 0, 1));
        rm2 cppm = new rm2(new Point3d(1, 1, 0));
        rm2 cppp = new rm2(new Point3d(1, 1, 1));

        public Result Research()
        {
            double LMez = LatoCubo / 2;
            int ln = allpoints.Count;
            for (int i = 0; i < ln; i++)
            {
                Point3d p3d = allpoints[i];
                double x = p3d.x;
                double y = p3d.y;
                double z = p3d.z;                
                rm2 pref = null;
                if (x < LMez && y < LMez && z < LMez) pref = cmmm;
                else if (x < LMez && y < LMez && z >= LMez) pref = cmmp;
                else if (x < LMez && y >= LMez && z < LMez) pref = cmpm;
                else if (x < LMez && y >= LMez && z >= LMez) pref = cmpp;
                else if (x >= LMez && y < LMez && z < LMez) pref = cpmm;
                else if (x >= LMez && y < LMez && z >= LMez) pref = cpmp;
                else if (x >= LMez && y >= LMez && z < LMez) pref = cppm;
                else if (x >= LMez && y >= LMez && z >= LMez) pref = cppp;

                double dst = p3d - pref.riferimento;
                if (dst < pref.cdist)
                {
                    pref.cdist = dst;
                    pref.punto = new Point3dIndex(p3d.x, p3d.y, p3d.z, i);
                }
            }

            double d1 = cmmm.punto - cppp.punto;
            Result r1 = new Result(d1, cmmm.punto.Index, cppp.punto.Index);

            double d2 = cmmp.punto - cppm.punto;
            Result r2 = new Result(d2, cmmp.punto.Index, cppm.punto.Index);

            double d3 = cmpm.punto - cpmp.punto;
            Result r3 = new Result(d3, cmpm.punto.Index, cpmp.punto.Index);

            double d4 = cmpp.punto - cpmm.punto;
            Result r4 = new Result(d4, cmpp.punto.Index, cpmm.punto.Index);

            Result CurrentResult = Result.Greatest(r1, r2);
            CurrentResult = Result.Greatest(CurrentResult, r3);
            CurrentResult = Result.Greatest(CurrentResult, r4);

            return CurrentResult;
        }
    }

    public class Universe
    {
        public List<Point3d> Allpoints;

        public Universe()
        {
            Allpoints = new List<Point3d>();
        }

        public void Load(string fname)
        {
            StreamReader sr = new StreamReader(fname);
            string stt = sr.ReadLine();
            string[] first = stt.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            int howmany = int.Parse(first[0]);
            LatoCubo = double.Parse(first[1]);
            string line;
            while ((line = sr.ReadLine()) != null)
            {
                string[] coords = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
                Allpoints.Add(new Point3d(double.Parse(coords[0]), double.Parse(coords[1]), double.Parse(coords[2])));
            }
            sr.Close();
        }

        public void Save(string fname)
        {
            StreamWriter sw = new StreamWriter(fname);
            sw.WriteLine("{0} {1}", Allpoints.Count, LatoCubo);
            foreach (Point3d p3d in Allpoints)
            {
                sw.WriteLine(p3d.ToString());
            }
            sw.Close();
        }

        public double LatoCubo;
        public void Generate(int npoints, double dim)
        {
            LatoCubo = dim;
            Allpoints.Clear();
            for (int t = 0; t < npoints; t++)
            {
                Allpoints.Add(Point3d.Rand(dim));
            }
        }
    }
}

[Vincenzo1968]

Originariamente inviato da gugoXX

Rimetto qui il codice, ma dovrebbe essere uguale a prima
...

Niente da fare. Ho sempre lo stesso problema

[gugoXX]

Originariamente inviato da Vincenzo1968

Niente da fare. Ho sempre lo stesso problema

giuro che a me funziona e non ho mai avuto neppure un problema.
Magari e' un probelma di memoria (non capisco come pero' a me possa funzionare sia con 100.000 che con 1.000.000 di punti).
Posso provare a dimezzare la memoria occupata, ma non so se il problema sta proprio li'

[Vincenzo1968]

Originariamente inviato da gugoXX

giuro che a me funziona e non ho mai avuto neppure un problema.
Magari e' un probelma di memoria (non capisco come pero' a me possa funzionare sia con 100.000 che con 1.000.000 di punti).
Posso provare a dimezzare la memoria occupata, ma non so se il problema sta proprio li'

Se è un problema di memoria, può essere dovuto al fatto che dispongo meno di 1 GB?
Questa è la mia macchina:

AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional (32 bit)
Service Pack 3

Ti posto il progetto Visual Studio e, a parte, l'eseguibile:

Progetto Visual Studio 2008:
http://www.guidealgoritmi.it/public/contest08AGugo.zip

Eseguibile:
http://www.guidealgoritmi.it/public/...08AGugoBin.zip

[gugoXX]

Originariamente inviato da Vincenzo1968

Se è un problema di memoria, può essere dovuto al fatto che dispongo meno di 1 GB?

Un regalino di Natale?
Scrivo io la letterina?

Progetto Visual Studio 2008:
http://www.guidealgoritmi.it/public/contest08AGugo.zip

Eseguibile:
http://www.guidealgoritmi.it/public/...08AGugoBin.zip

Lo zip dell'eseguibile e' corrotto (problemi di memoria? )

[banryu79]

Originariamente inviato da gugoXX

Lo zip dell'eseguibile e' corrotto (problemi di memoria? )

No, semplicemente è italiano.

(battuta orribile e qualunquista, lo so, perdonatemi ma oggi in ufficio c'è la desolazione più totale e io sono in modalità cazzeggio-prenatalizio).

[Vincenzo1968]

Originariamente inviato da gugoXX

Un regalino di Natale?
Scrivo io la letterina?



Lo zip dell'eseguibile e' corrotto (problemi di memoria? )

Li mortan guerieri!!!
L'ho ricompilato più de na vorta, ma mme dà sempre li stessi problemi. Li mortan de li mortan guerieri!!!
Me poi posta l'eseguibile tuo?

[Vincenzo1968]

Ho ricompilato. Prova con questo:

http://www.guidealgoritmi.it/public/contest08aGugo.zip

[Tommo]

M'è venuta un'idea per trovare la distanza massima, che dovrebbe essere molto più veloce... non so però se sia esatta:

Invece che provare tutti i "miniscatoli" (che sarebbero octree cells ma vabè ) è facile capire quale è quello che contiene la coppia a distanza massima.

Preso un punto P qualsiasi:
-dividi la "scatola universo" in 8 "sottovolumi" per P
-sono definiti dai 3 piani allineati agli assi passanti per P
-la celletta che contiene il punto più distante è quella contenuta nel sottovolume di volume maggiore, e che a sua volta contiene uno dei vertici del cubo universo.
-Si fa quindi la distanza tra P ed ogni punto contenuto nella celletta trovata, in media meno di 10 iterazioni.

In questa maniera il tutto sarebbe praticamente lineare, e dovrebbe metterci infinitamente meno di ora... però non so come comportarmi nel caso che la cella trovata sia vuota.

Cmq per trovare la coppia a distanza massima basta calcolarsi i punti nelle 4 coppie di celle ai lati opposti della diagonale del cubo, credo.

[gugoXX]

Originariamente inviato da Tommo

M'è venuta un'idea per trovare la distanza massima, che dovrebbe essere molto più veloce... non so però se sia esatta:

Invece che provare tutti i "miniscatoli" (che sarebbero octree cells ma vabè ) è facile capire quale è quello che contiene la coppia a distanza massima.

Preso un punto P qualsiasi:
-dividi la "scatola universo" in 8 "sottovolumi" per P
-sono definiti dai 3 piani allineati agli assi passanti per P
-la celletta che contiene il punto più distante è quella contenuta nel sottovolume di volume maggiore, e che a sua volta contiene uno dei vertici del cubo universo.
-Si fa quindi la distanza tra P ed ogni punto contenuto nella celletta trovata, in media meno di 10 iterazioni.

In questa maniera il tutto sarebbe praticamente lineare, e dovrebbe metterci infinitamente meno di ora... però non so come comportarmi nel caso che la cella trovata sia vuota.

Cmq per trovare la coppia a distanza massima basta calcolarsi i punti nelle 4 coppie di celle ai lati opposti della diagonale del cubo, credo.

E' l'algoritmo implementato da me...
Ma e' greedy, nel senso che puo' sbagliare. Il piu' delle volte trova una soluzione molto buona, su grandi numeri (casuali) trova spesso la soluzione ottima.
Ma appunto non c'e' garanzia, puo' anche sbagliare.

[gugoXX]

Originariamente inviato da Vincenzo1968

Ho ricompilato. Prova con questo:

http://www.guidealgoritmi.it/public/contest08aGugo.zip

Funziona subito...

[Vincenzo1968]

Originariamente inviato da gugoXX

Funziona subito...

E allora è un problema di memoria?