Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumsweep-line

Minimum Area Rectangle

Problem (yeniden ifade)

Düzlemde ayrık noktalar verildiğinde, belirledikleri eksen-hizalı dikdörtgenin minimum alanını döndür; yoksa 0.

Sezgi

Eksen-hizalı dikdörtgen, dört köşesi de var olan iki farklı x ve iki farklı y’dir. Dikey doğruları soldan sağa süpür: her x çiftinde paylaşılan y’ler yatay kenar adaylarıdır. Sabit genişlikte en küçük yükseklik, paylaşılan y’lerin en yakın çiftidir.

Yaklaşımlar

Dikey doğruları süpür

Doğrulanmadı

Zaman O(n²)Alan O(n)

Fikir. x → y kümesi map. x’leri sırala. Her x1 < x2 çifti için y kümelerini kesiştir, ortak y’leri sırala, ardışık çiftleri dene: alan dx * dy. Min tut; yoksa 0.

Yürüyüş. (1,1),(1,3),(3,1),(3,3) x=1 ve x=3’te y=3 paylaşır → alan 4. Bu doğrulardaki ekstra noktalar yalnızca dy’yi küçültür.

Trade-off. Ardışık paylaşılan y yeter: genişlik sabit, min yükseklik en yakın çift. Her iki noktayı köşegen almak aynı karmaşıklık, daha dağınık. Dikdörtgen yok → 0, sonsuz değil.

Çözüm

export function minAreaRect(points: number[][]): number {
  const byX = new Map<number, Set<number>>();
  for (const p of points) {
    const x = p[0]!, y = p[1]!;
    if (!byX.has(x)) byX.set(x, new Set());
    byX.get(x)!.add(y);
  }
  const xs = [...byX.keys()].sort((a, b) => a - b);
  let ans = Infinity;
  for (let i = 0; i < xs.length; i++) {
    const ys1 = byX.get(xs[i]!)!;
    for (let j = i + 1; j < xs.length; j++) {
      const common: number[] = [];
      for (const y of byX.get(xs[j]!)!) if (ys1.has(y)) common.push(y);
      if (common.length < 2) continue;
      common.sort((a, b) => a - b);
      const dx = xs[j]! - xs[i]!;
      for (let k = 1; k < common.length; k++) {
        const area = dx * (common[k]! - common[k - 1]!);
        if (area < ans) ans = area;
      }
    }
  }
  return ans === Infinity ? 0 : ans;
}

export function minAreaRect(points: number[][]): number {
  const byX = new Map<number, Set<number>>();
  for (const p of points) {
    const x = p[0]!, y = p[1]!;
    if (!byX.has(x)) byX.set(x, new Set());
    byX.get(x)!.add(y);
  }
  const xs = [...byX.keys()].sort((a, b) => a - b);
  let ans = Infinity;
  for (let i = 0; i < xs.length; i++) {
    const ys1 = byX.get(xs[i]!)!;
    for (let j = i + 1; j < xs.length; j++) {
      const common: number[] = [];
      for (const y of byX.get(xs[j]!)!) if (ys1.has(y)) common.push(y);
      if (common.length < 2) continue;
      common.sort((a, b) => a - b);
      const dx = xs[j]! - xs[i]!;
      for (let k = 1; k < common.length; k++) {
        const area = dx * (common[k]! - common[k - 1]!);
        if (area < ans) ans = area;
      }
    }
  }
  return ans === Infinity ? 0 : ans;
}

Şablon bağlantısı

Dikey doğruları süpür, her olay x çiftinde 1D örtüşme (paylaşılan y’ler). Dikdörtgen süpürmenin “x’e göre sırala, aktif y-kümesine bak” iskeleti; noktaların genişliği olmadığı için enter/exit yok.

Yansıma

Aynı x’teki y’ler bir doğru. İki x arasında ortak y’ler. Ardışık ortak y çifti bir dikdörtgen. Alan dx * dy.
Ortak y yoksa dikdörtgen yok, cevap 0. En küçük pozitif alan.
Eğik kenar sayılmaz. Üç nokta yetmez. Aynı nokta iki kez alan üretmez.