아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Skriestuvas

시간 제한1초메모리 제한1024 MB

요약
직사각형 위에 그린 원들이 서로 만나거나 닿을 때만 이동할 수 있다고 할 때, 종이 가장자리까지 경로가 있는 원의 개수를 센다.
난이도

보통10점 중 6점

유형
유니온 파인드, 기하, 그래프
정답자
아직 제출이 없습니다

문제

Mažasis Vilius gavo dovanų skriestuvą ir pradėjo mokytis piešti apskritimus. Galiausiai jis pripiešė visą lapą įvairiausio dydžio apskritimų. Kai kurie apskritimai kertasi, taip pat kai kurie iš jų kerta arba liečia sąsiuvinio kraštą, kaip pavaizduota žemiau:

Žiūrėdamas į šį lapą, pilną apskritimų, Vilius sugalvojo sau žaidimą: besti pieštuku ant bet kurio apskritimo lanko ir ieškoti kelio, einančio tik nubrėžtų apskritimų lankais, iki popieriaus lapo krašto. Pagal Viliaus taisykles, šis kelias gali pereiti nuo vieno apskritimo į kitą tiktai jei tie du apskritimai kertasi arba liečiasi.

Jums žinomas lapo dydis bei visų nubrėžtų apskritimų koordinatės ir dydžiai. Raskite, kiek yra tokių apskritimų, iš kurių Vilius gali surasti kelią iki lapo krašto pagal aukščiau nurodytas taisykles.

입력

Pirmojoje eilutėje įrašytas lapo plotis L_xL\_x ir aukštis L_yL\_y – abu sveikieji skaičiai. Antrojoje eilutėje įrašytas Viliaus nubrėžtų apskritimų skaičius NN.

Toliau pateikta NN eilučių, kuriose aprašyti Viliaus nubrėžti apskritimai. Kiekvienoje iš jų įrašyti trys sveikieji skaičiai: apskritimo centro koordinatės lape x_ix\_i ir y_iy\_i, bei apskritimo spindulys r_ir\_i.

Koordinatės (0,0)(0, 0) atitinka apatinį kairįjį popieriaus lapo kampą. Taip pat galioja ribojimai:

  • 0≤x_i≤L_x0 ≤ x\_i ≤ L\_x;
  • 0≤y_i≤L_y0 ≤ y\_i ≤ L\_y;
  • r_ir\_i nėra ilgesnis už pusę ilgesniosios lapo kraštinės.

출력

Išveskite vienintelį skaičių – kiek yra tokių apskritimų, iš kurių Vilius gali surasti kelią iki lapo krašto pagal savo žaidimo taisykles.

제한

  • 1≤L_x,L_y,r_i≤1,000,0001 ≤ L\_x, L\_y, r\_i ≤ 1\\, 000\\, 000
  • 1≤N≤10,0001 ≤ N ≤ 10\\, 000

예제1

  1. 예제 1

    입력
    16 20
8
8 15 1
8 16 4
16 12 4
12 8 6
11 6 3
4 12 2
0 8 3
4 3 2
    예상 출력
    5