Fişierul intrare/ieşire:distancesum.in, distancesum.outSursăHappy Birthday Infoarena 2014
AutorAndrei HeidelbacherAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test0.7 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

DistanceSum

Se dau N puncte în plan şi M întrebări de forma: "care este suma distanţelor de la fiecare din cele N puncte la punctul (x, y) dat?".
Distanţa dintre doua puncte (x1, y1) şi (x2, y2) este max(|x2 - x1|, |y2 - y1|).

Date de intrare

Fişierul de intrare distancesum.in conţine pe prima linie numerele N şi M. Pe următoarele N linii se găsesc numerele xi şi yi reprezentând coordonatele celor N puncte din plan. Pe următoarele M linii se găsesc numerele xi şi yi semnificând coordonatele punctelor din întrebări.

Date de ieşire

În fişierul de ieşire distancesum.out veţi afişa M numere, câte unul pe linie, reprezentând răspunsurile la întrebări.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 100.000
  • Toate coordonatele sunt numere întregi cuprinse între -109 şi 109

Exemplu

distancesum.indistancesum.out
4 3
3 5
-3 -2
1 4
-4 -3
2 -4
1 4
4 2
28
15
21
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?