系統設計

1type Hit = { driver: string; km: number };
2 
3class GridIndex {
4  private cells = new Map<string, Set<string>>();
5  private where = new Map<string, { x: number; y: number; cell: string }>();
6 
7  constructor(private cellKm: number, private cityKm: number) {}
8 
9  cellOf(x: number, y: number): string {
10    return `${Math.floor(x / this.cellKm)},${Math.floor(y / this.cellKm)}`;
11  }
12 
13  update(driver: string, x: number, y: number): void {
14    const cell = this.cellOf(x, y);
15    const old = this.where.get(driver);
16    if (old && old.cell !== cell) this.cells.get(old.cell)?.delete(driver);
17    if (!old || old.cell !== cell) {
18      if (!this.cells.has(cell)) this.cells.set(cell, new Set());
19      this.cells.get(cell)!.add(driver);
20    }
21    this.where.set(driver, { x, y, cell });
22  }
23 
24  remove(driver: string): void {
25    const old = this.where.get(driver);
26    if (!old) return;
27    this.cells.get(old.cell)?.delete(driver);
28    this.where.delete(driver);
29  }
30 
31  nearby(x: number, y: number, k: number): Hit[] {
32    const cx = Math.floor(x / this.cellKm), cy = Math.floor(y / this.cellKm);
33    const found: Hit[] = [];
34    const maxRing = Math.ceil(this.cityKm / this.cellKm) + 1;
35    for (let r = 0; r <= maxRing; r++) {
36      for (let dx = -r; dx <= r; dx++) {
37        for (let dy = -r; dy <= r; dy++) {
38          if (Math.max(Math.abs(dx), Math.abs(dy)) !== r) continue;
39          for (const driver of this.cells.get(`${cx + dx},${cy + dy}`) ?? []) {
40            const at = this.where.get(driver)!;
41            found.push({ driver, km: Math.hypot(at.x - x, at.y - y) });
42          }
43        }
44      }
45      found.sort((a, b) => a.km - b.km || (a.driver < b.driver ? -1 : 1));
46      // Anything not yet seen is at least r cells away.
47      if (found.length >= k && found[k - 1].km <= r * this.cellKm) break;
48    }
49    return found.slice(0, k);
50  }
51}