en C#, vous travaillez comme stagaire dans un centre de recherche effectuant des expériences avec un accelerateur de particules. Vous devez trouver les deux particules qui pourraient etre des bosons de Higgs, parmi toutes celles resultant d'une collision. Ces particules sont fournies sous la forme d'une liste de coordonnées [x,y]. Vos grandes connaissances scientifiques vous laissent supposer qu'un boson de Higgs est un particule amicale, qui essaie toujours d'etre aussi proche que possible d'un autre boson de Higgs. Vous devez donc trouver les deux particules ayant la plus petite distance euclidienne entre elles, et renvoyer leur deux index.
Ecrit fonction public static List<int> FindHiggs(List<List<int>> particules).
Contraints:
les coordonnees des particules sont des entiers;
il n'y aura jamais deux paires de particules differentes ayant la meme distance minimale;
il y a au moins 2 particules et au plus 20000 particules;
La paire de particules la plus proche sera toujours distante d'au plus 1000 unité;
pour tout carre de taille 1000x1000 , il y a au plus 100 particules dans ce carre. compte tenu de ces contraintes, vous ne devriez pas calculer toues les distance entre toutes les particules, car cela prendrait trop de temps. Il pourrait etre judicieux de les indexer en utilisant un quadrillage.
using System;
using System.Collections.Generic;
public class ParticleDetector
{
public static List<int> FindHiggs(List<List<int>> particules)
{
var grid = new Dictionary<(int, int), List<(int index, int x, int y)>>();
// Remplit la grille en indexant les particules par leurs cellules
foreach (var particule in particules)
{
int x = particule[0];
int y = particule[1];
// Calcul des coordonnées de la cellule
int cellX = x / 1000;
int cellY = y / 1000;
// Ajoute la particule à la cellule correspondante
if (!grid.ContainsKey((cellX, cellY)))
{
grid[(cellX, cellY)] = new List<(int, int, int)>();
}
grid[(cellX, cellY)].Add((grid[(cellX, cellY)].Count, x, y)); // Stocke l'index basé sur l'ordre d'ajout
}
double minDistanceSquared = double.MaxValue; // On utilise la distance au carré pour éviter la racine carrée
int index1 = -1, index2 = -1;
// Parcourt chaque cellule et les cellules voisines
foreach (var cell in grid)
{
var (cellX, cellY) = cell.Key;
var particlesInCell = cell.Value;
// Vérifie les cellules voisines
for (int dx = -1; dx <= 1; dx++)
{
for (int dy = -1; dy <= 1; dy++)
{
var neighborCellKey = (cellX + dx, cellY + dy);
if (grid.ContainsKey(neighborCellKey))
{
var neighborParticles = grid[neighborCellKey];
// Compare chaque paire de particules entre la cellule actuelle et la voisine
foreach (var particle1 in particlesInCell)
{
foreach (var particle2 in neighborParticles)
{
// On évite de comparer une particule avec elle-même
if (particle1.index != particle2.index)
{
double distanceSquared = CalculateDistanceSquared(particle1.x, particle1.y, particle2.x, particle2.y);
// Mise à jour si une plus petite distance est trouvée
if (distanceSquared < minDistanceSquared)
{
minDistanceSquared = distanceSquared;
index1 = particle1.index;
index2 = particle2.index;
}
}
}
}
}
}
}
}
// Retourne les indices des deux particules les plus proches
return new List<int> { index1, index2 };
}
// Méthode pour calculer la distance au carré entre deux points
private static double CalculateDistanceSquared(int x1, int y1, int x2, int y2)
{
return Math.Pow(x2 - x1, 2) + Math.Pow(y2 - y1, 2);
}
}
Aucun commentaire:
Enregistrer un commentaire