Nöqtələrin əlavə edilməsi və silinməsi

Hər N^2 log N eyni dərəcədə faydalı deyil...

Hansısa mühazirə

Sizin müstəvidə A nöqtələrinin çoxluq çoxluğu var.

Üç növ sorğunu emal etməyi öyrənməlisiniz:

• Nöqtəni çoxluq çoxluğuna A əlavə etmək

• Nöqtəni çoxluq çoxluğundan A silmək

• Hesablamaq

  

  distance(p, q).

Giriş verilənləri

Sorğuların sayı N (1 ≤ N ≤ 3000). Sonra N sətir, sorğuları təsvir edir, dəqiq formatı nümunədə baxın. Nöqtələrin koordinatları 0 ilə 3000 arasında tam ədədlərdir. Nöqtələr üst-üstə düşə bilər. Nöqtəni silmək sorğusu dəqiq bir nöqtəni silməlidir (sorğu anında belə bir nöqtənin çoxluq çoxluğunda olduğu təmin edilir).

Çıxış verilənləri

Hər çoxluq əməliyyatından sonra cari maksimum məsafələrin cəmini çıxarın. Mütləq səhv 10^{-6}-dan çox olmamalıdır.

Nümunələr