Đường thẳng độc lập
Đề bài
Mô tả
Cho tập gồm điểm trên mặt phẳng, điểm thứ có tọa độ . Vẽ đoạn thẳng nối mọi cặp điểm. Một đường thẳng được gọi là độc lập đối với tập nếu nó không cắt bất kỳ đoạn thẳng nào trong số này tại bất kỳ điểm nào (kể cả chỉ chạm đầu mút).
Yêu cầu: Cho đường thẳng, hãy đếm số đường thẳng độc lập đối với tập . Mỗi đường thẳng được cho bởi ba tham số ứng với phương trình .
Dữ liệu vào
Dòng đầu tiên chứa số nguyên dương (): số bộ dữ liệu. Mỗi bộ dữ liệu có cấu trúc như sau:
- Dòng đầu tiên chứa số nguyên ().
- dòng tiếp theo, dòng thứ chứa hai số nguyên (): tọa độ của điểm thứ . Các điểm có thể trùng nhau.
- Dòng tiếp theo chứa số nguyên dương ().
- dòng cuối, dòng thứ chứa ba số nguyên (, và không đồng thời bằng ): phương trình của đường thẳng thứ .
Dữ liệu ra
In ra dòng, dòng thứ chứa một số nguyên là số đường thẳng độc lập đối với tập trong bộ dữ liệu thứ .
Ràng buộc
- ,
- ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 3 0 1 1 0 -1 0 4 1 -1 0 1 0 3 0 1 0 1 0 -1 |
1 | Ví dụ của đề gốc. Chỉ đường thẳng thứ hai () là độc lập. Đường chứa đoạn nối và , đường đi qua điểm . |
| 1 4 0 0 2 0 0 2 2 2 5 1 0 -3 1 0 -2 1 1 -1 1 1 1 1 -1 3 |
3 | Ví dụ bổ sung, tính bằng lời giải mẫu. Các đường , và là độc lập; chứa cạnh của hình vuông, cắt đoạn nối và . |
Bình luận