Nghệ thuật trường tồn
Đề bài
Mô tả
Bạn vừa có cảm hứng và đang thiết kế một tác phẩm điêu khắc mới thật đẹp đặt ở sảnh của bảo tàng địa phương. Vì những lý do nghệ thuật cực kỳ quan trọng, bạn thiết kế nó bằng những vật liệu rất đặc biệt. Tuy nhiên, bạn không chắc các định luật vật lý có đứng về phía mình hay không. Liệu tác phẩm có thực sự đứng vững được không?
Tác phẩm gồm nhiều khớp cầu, mỗi khớp nặng kilôgam, và nhiều thanh (khối lượng không đáng kể) nối các khớp với nhau. Các thanh không thể bị kéo giãn hay nén lại, và không bao giờ rời khỏi khớp. Tuy nhiên, chúng có thể quay tự do quanh các khớp theo mọi hướng. Các khớp nằm trên mặt đất được dán cố định tại chỗ; mọi khớp khác đều có thể chuyển động. Để đơn giản, bạn có thể bỏ qua việc các thanh cắt nhau; mỗi thanh chỉ tác dụng lực lên khớp mà nó nối. Ngoài ra, mọi khớp nằm trên không đều có ít nhất một thanh nối với nó không song song với mặt đất. Điều này loại trừ trường hợp suy biến khi một khớp chỉ được đỡ theo phương ngang bởi một kết cấu cứng (ngoài đời thực, nó sẽ võng xuống một chút).
Hãy viết chương trình xác định kết cấu có tĩnh hay không (tức là không lập tức chuyển động dưới tác dụng của trọng lực). Lưu ý rằng mỗi thanh có thể truyền một lực căng lớn tuỳ ý dọc theo chiều dài của nó, và "tĩnh" có nghĩa là tại mỗi khớp, các lực căng cân bằng với trọng lượng của khớp.
Nếu kết cấu tĩnh, bạn còn phải xác định nó có ổn định hay không (tức là không chuyển động khi bị nhiễu nhẹ bằng cách kéo các khớp của nó).
Dữ liệu vào
Dữ liệu gồm nhiều mô tả tác phẩm. Mỗi mô tả bắt đầu bằng một dòng chứa hai số nguyên và , lần lượt là số khớp và số thanh của kết cấu. Các khớp được đánh số từ đến . Tiếp theo là dòng, mỗi dòng ứng với một khớp, gồm số thực là toạ độ của khớp đó. Sau đó là dòng, mỗi dòng ứng với một thanh, gồm số nguyên phân biệt là chỉ số hai khớp mà thanh đó nối.
Mỗi thanh có độ dài vừa đúng để nối hai khớp của nó. Toạ độ luôn không âm; toạ độ bằng nghĩa là khớp nằm trên mặt đất và được cố định tại chỗ.
Sau mô tả cuối cùng là một dòng chứa hai số .
Dữ liệu ra
Với mỗi mô tả tác phẩm, in NON-STATIC (không tĩnh), UNSTABLE (tĩnh nhưng không ổn định) hoặc STABLE (ổn định) theo định dạng như ví dụ: Sculpture i: rồi đến kết luận, với là số thứ tự của tác phẩm, bắt đầu từ .
Ràng buộc
- , .
- , ; mỗi toạ độ có không quá chữ số sau dấu chấm thập phân.
- Hai khớp được nối bởi một thanh có toạ độ khác nhau.
- Mọi khớp có đều có ít nhất một thanh nối với một khớp có toạ độ khác nó.
- Mỗi file có không quá tác phẩm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 3 0 0 0 -1.0 -0.5 1.0 1.0 -0.5 1.0 0 1.0 1.0 1 2 1 3 1 4 4 6 0 0 0 -1.0 -0.5 1.0 1.0 -0.5 1.0 0 1.0 1.0 1 2 1 3 1 4 2 3 2 4 3 4 7 9 0 0 0 -1.0 -0.5 1.0 1.0 -0.5 1.0 0 1.0 1.0 -1.0 -0.5 0 1.0 0.5 0 0 1.0 0 1 2 1 3 1 4 2 3 2 4 3 4 2 5 3 6 4 7 0 0 |
Sculpture 1: NON-STATIC Sculpture 2: UNSTABLE Sculpture 3: STABLE |
Tác phẩm 1: mỗi khớp trên không chỉ treo bằng một thanh xiên nên không thể cân bằng trọng lượng. Tác phẩm 2: tứ diện đứng trên một điểm, trọng tâm nằm đúng phía trên điểm tựa nên tĩnh, nhưng có thể xoay quanh điểm tựa. Tác phẩm 3: thêm ba chân xuống đất làm kết cấu ổn định. |
| 2 1 0 0 0 0 0 2.5 1 2 3 2 1 0 0 -1 0 0 0 1 1 1 3 2 3 5 6 0 0 0 1 0 0 0 1 0 0 0 1 1 1 2 1 4 2 4 3 4 4 5 2 5 3 5 3 2 1 0 0 -1 0 0 0 0 1 1 3 2 3 0 0 |
Sculpture 1: UNSTABLE Sculpture 2: NON-STATIC Sculpture 3: STABLE Sculpture 4: UNSTABLE |
Ví dụ tự thêm. Tác phẩm 1: một cột thẳng đứng chịu được trọng lượng nhưng có thể đổ nghiêng. Tác phẩm 2: khớp treo trên hai thanh quay quanh trục , nằm lệch khỏi trục nên sẽ rơi. Tác phẩm 3: khớp đứng trên ba chân, khớp nối với nó và hai điểm trên đất. Tác phẩm 4: như tác phẩm 2 nhưng khớp nằm đúng phía trên trục quay nên tĩnh, vẫn có thể lắc quanh trục. |
Bình luận