trang chủ / đề bài / icpcwf10_h

Mưa

Đề bài

Mô tả

Những năm gần đây, các cơn bão và sóng thần đã cho thấy sức tàn phá của nước. Tuy nhiên, sức tàn phá ấy không chỉ đến từ biển. Mưa lớn có thể gây lũ lụt, phá hủy nhà cửa và ruộng đồng. Bằng các mô hình phức tạp, các nhà khoa học cố gắng dự đoán nơi nước sẽ đọng lại sau một trận mưa lớn.

Một cách mô hình hóa địa hình đồi núi là tam giác phân: xấp xỉ bề mặt bằng các tam giác. Mỗi cạnh của một tam giác được dùng chung hoàn toàn bởi hai tam giác kề nhau, trừ các tam giác ở biên của vùng, chúng có thể có một số cạnh không dùng chung với tam giác nào.

Hãy hình dung bạn có mô hình tam giác phân của một vùng địa hình. Mưa bắt đầu đổ xuống: một phần nước chảy ra biển, phần còn lại bị địa hình giữ lại tạo thành các hồ. Nhiệm vụ của bạn là viết chương trình xác định có bao nhiêu hồ được tạo thành và mực nước của từng hồ. Giả sử mưa đủ lớn để mọi hồ đều được đổ đầy tới mực nước tối đa của nó.

Với mỗi hồ, có thể chèo thuyền giữa hai điểm bất kỳ trên mặt hồ (trừ phần biên) bằng một chiếc thuyền có kích thước nhỏ tùy ý nhưng khác 0. Do đó, nếu hai hồ chỉ có chung các điểm (hoặc một điểm) có độ sâu bằng 0 thì chúng được coi là hai hồ khác nhau.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên p (p≥3) là số điểm và s (s≥3) là số cạnh của tam giác phân. Mỗi dòng trong p dòng tiếp theo mô tả một điểm của tam giác phân.

Mô tả của mỗi điểm bắt đầu bằng một mã gồm hai chữ cái, duy nhất trong bộ test. Tiếp theo là ba số nguyên mô tả điểm theo dạng x y h. Trong đó x và y (−10000≤x,y≤10000) là tọa độ trên mặt phẳng và h (0≤h≤8848) là độ cao của điểm so với mực nước biển.

Mỗi dòng trong s dòng tiếp theo mô tả một cạnh của tam giác, gồm hai mã hai chữ cái khác nhau là hai đầu mút của cạnh. Hình chiếu của các cạnh xuống mặt phẳng xy thỏa mãn các điều kiện sau:

  • Không có cạnh nào cắt cạnh khác, trừ tại các đầu mút.
  • Các điểm và các cạnh cùng nhau tạo thành một tam giác phân của một vùng liên thông duy nhất.
  • Vùng không có "lỗ" bên trong (tức là biên của vùng tạo thành một đường gấp khúc khép kín duy nhất).

Có thể coi mọi điểm nằm ngoài vùng tam giác phân đều thấp hơn điểm gần nhất trên biên của vùng. Nói cách khác, nếu nước chạm tới biên của vùng thì nó chảy ra ngoài tự do.

Dòng cuối cùng của dữ liệu vào chứa hai số 0.

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test và mực nước của tất cả các hồ khác nhau nằm trong vùng đã cho, mỗi mực nước trên một dòng. Mực nước là độ cao so với mực nước biển và phải được in theo thứ tự không giảm. Nếu không có hồ nào được tạo thành, in ra một số 0 duy nhất. Làm theo đúng định dạng trong ví dụ.

Ràng buộc

  • 3≤p≤2704 (mỗi mã gồm hai chữ cái tiếng Anh, phân biệt chữ hoa và chữ thường, nên có nhiều nhất 522=2704 mã khác nhau), s≥3.
  • −10000≤x,y≤10000, 0≤h≤8848, các điểm có tọa độ (x,y) đôi một khác nhau.
  • Tổng p của mọi bộ test trong một file không vượt quá 30000.

Ví dụ

Input Output Giải thích
3 3
AA 0 0 0
BB 0 1 0
CC 1 0 0
AA BB
AA CC
BB CC
7 12
aa 1 1 5
bb 1 3 5
xX 0 2 10
XY 0 4 15
XZ 3 4 11
xy 0 0 15
xz 3 0 15
xX XZ
XY XZ
xX XY
xX xy
xX xz
xz xy
aa xX
aa xy
aa xz
bb xX
bb XY
bb XZ
0 0
Case 1:
0
Case 2:
10
10
Bộ 1: một tam giác phẳng, không giữ được nước. Bộ 2: vùng gồm hai tam giác lớn chỉ chạm nhau tại điểm xX (độ cao 10), mỗi tam giác được chia thành ba tam giác nhỏ quanh điểm aa hoặc bb (độ cao 5). Nước quanh aa dâng tới độ cao 10 thì tràn ra ngoài qua điểm xX, quanh bb cũng vậy. Hai hồ chỉ chung điểm xX có độ sâu 0 nên là hai hồ khác nhau, cùng mực nước 10.
9 16
Aa 0 0 9
Ab 1 0 4
Ac 2 0 9
Ba 0 1 9
Bb 1 1 1
Bc 2 1 9
Ca 0 2 9
Cb 1 2 9
Cc 2 2 9
Aa Ab
Ab Ac
Ba Bb
Bb Bc
Ca Cb
Cb Cc
Aa Ba
Ba Ca
Ab Bb
Bb Cb
Ac Bc
Bc Cc
Aa Bb
Ab Bc
Ba Cb
Bb Cc
12 23
Pa 0 0 9
Pb 1 0 9
Pc 2 0 9
Pd 3 0 9
Qa 0 1 9
Qb 1 1 2
Qc 2 1 3
Qd 3 1 9
Ra 0 2 9
Rb 1 2 9
Rc 2 2 9
Rd 3 2 9
Pa Pb
Pb Pc
Pc Pd
Qa Qb
Qb Qc
Qc Qd
Ra Rb
Rb Rc
Rc Rd
Pa Qa
Pb Qb
Pc Qc
Pd Qd
Qa Ra
Qb Rb
Qc Rc
Qd Rd
Pa Qb
Pb Qc
Pc Qd
Qa Rb
Qb Rc
Qc Rd
0 0
Case 1:
4
Case 2:
9
Bộ 1: lưới 3×3, điểm giữa Bb cao 1, điểm Ab trên biên cao 4, mọi điểm khác cao 9. Nước quanh Bb dâng tới độ cao 4 thì tràn ra ngoài qua Ab. Bộ 2: lưới 4×3 có hai điểm trong Qb (độ cao 2) và Qc (độ cao 3) nối với nhau bằng một cạnh, mọi điểm biên cao 9: hai chỗ trũng gộp thành một hồ duy nhất có mực nước 9.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0