Qonşular#5475

Qonşular

3 saniyə
64 meqabayt
Çətin

Dekart müstəvisində və koordinatları ilə müəyyən olunan bir düzbucaqlını nəzərdən keçirək, burada və müsbət tam ədədlərdir. Bu düzbucaqlıda, şəbəkə nöqtələrində yerləşən dağ zirvəsi mövcuddur (şəbəkə nöqtəsi — tam ədədlərlə verilən koordinatlara malik nöqtədir). Hər kəs ev tikmək istəyir, lakin aşağıdakı qaydalar tətbiq olunur:

- Hər şəbəkə nöqtəsində ən çox bir ev tikilə bilər. - Dağ zirvələrində ev tikmək olmaz.

Beləliklə, (w+1)\times(h+1)-N mümkün ev tikinti yeri məvcuddur. Bəzi yerlər digərlərindən üstün hesab olunur. nöqtəsi üçün şimal qonşusu mövcuddur əgər (x, y+d) nöqtəsində bir zirvə varsa, burada müsbət tam ədəddir. Eyni qaydada cənub, şərq və qərb qonşuları da müəyyən edilir. Beləliklə, zirvə olmayan hər bir şəbəkə nöqtəsinin -dan -dək qonşusu ola bilər. Qonşuların sayı artdıqca, yer daha əlverişli hesab olunur. Tapşırığınız — zirvələr nəzərə alınmadan, neçə şəbəkə nöqtəsinin dəqiq , , , və ya qonşusu olduğunu hesablamaqdır.

Proqram yazın, hansı ki:

- Ərazinin təsvirini standart girişdən oxuyur. - Dəqiq , , , , qonşuya malik olan nöqtələrin sayını hesablayır. - Nəticəni standart çıxışa çıxarır.

Giriş

Birinci sətir , , (1 \leq w, h \leq 10^9), (1 \leq N \leq 500000) tam ədədlərini ehtiva edir və bu ədədlər boşluqla ayrılır. Sonrakı sətrin hər biri iki tam ədəd və (0 \leq x \leq w), (0 \leq y \leq h), boşluqla ayrılmış, bir zirvənin koordinatlarını göstərir. Bütün zirvələr müxtəlif nöqtələrdə yerləşir.

Çıxış

Çıxışın birinci və yeganə sətirində tam ədəd — zirvələr istisna olmaqla, , , , , qonşuya malik olan nöqtələrin sayı verilir (ədədlər boşluqla ayrılır).

Nümunələr

Nümunə 1

Loading
Loading