Phosphorus nghiên cứu đa giác
Đề bài
Mô tả
Phosphorus đã vẽ đa giác đều trên mặt phẳng tọa độ Descartes. Các đa giác được đánh số từ đến .
Mỗi đa giác đều thứ được mô tả bởi tọa độ tâm , khoảng cách từ tâm đến các đỉnh (bán kính đường tròn ngoại tiếp) và số cạnh . Để tránh nhập nhằng về góc xoay, giả sử luôn có một đỉnh của đa giác thứ nằm đúng tại , đỉnh còn lại cách đều nhau trên đường tròn ngoại tiếp.
Ta nói hai đa giác giao nhau nếu chúng có ít nhất một điểm chung (tính cả các điểm trên biên lẫn bên trong). Lưu ý rằng một đa giác luôn giao với chính nó.
Đảm bảo rằng khi hai đa giác không giao nhau thì khoảng cách Euclid nhỏ nhất giữa chúng ít nhất là . Ở đây, khoảng cách giữa hai đa giác là khoảng cách nhỏ nhất giữa một điểm thuộc đa giác thứ nhất và một điểm thuộc đa giác thứ hai. Đảm bảo này không loại trừ các đa giác chạm nhau: hai đa giác chạm nhau được coi là giao nhau và có khoảng cách bằng .
Phosphorus sẽ đưa ra truy vấn. Mỗi truy vấn gồm một số nguyên (). Với mỗi truy vấn, xét tất cả các đa giác giao với đa giác thứ . Trong số các đa giác đó, hãy tìm chỉ số () của đa giác có tổng diện tích lớn nhất.
Gợi ý: Diện tích của đa giác đều có cạnh và bán kính đường tròn ngoại tiếp được tính theo công thức . Đảm bảo rằng khi hai đa giác có cặp khác nhau thì diện tích lớn hơn gấp ít nhất lần diện tích nhỏ hơn, vì vậy tính công thức này bằng kiểu số thực 64 bit thông thường (ví dụ double trong C++ và Java, hoặc float trong Python) là đủ chính xác để so sánh diện tích.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và (): số đa giác và số truy vấn.
- dòng tiếp theo, mỗi dòng chứa bốn số nguyên , , và (, , ): tọa độ tâm, bán kính đường tròn ngoại tiếp và số cạnh của đa giác thứ .
- dòng tiếp theo, mỗi dòng chứa một số nguyên (): chỉ số của đa giác trong truy vấn hiện tại.
Dữ liệu ra
In ra dòng. Với truy vấn thứ , in ra một số nguyên : chỉ số của đa giác có tổng diện tích lớn nhất trong các đa giác giao với đa giác . Nếu có nhiều đa giác giao với cùng có diện tích lớn nhất, in ra đa giác có chỉ số nhỏ nhất.
Ràng buộc
- .
- , , .
- .
- Hai đa giác không giao nhau thì cách nhau ít nhất .
- Hai đa giác có cặp khác nhau thì tỉ số diện tích (lớn chia nhỏ) ít nhất là .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 0 0 2 3 2 0 2 3 6 0 3 3 0 5 2 3 1 2 3 4 |
1 3 3 4 |
Bốn tam giác đều, mỗi tam giác có một đỉnh hướng lên trên. Tam giác 1 chỉ giao với tam giác 2, hai tam giác có cùng diện tích nên chọn chỉ số nhỏ hơn là 1. Tam giác 2 giao với tam giác 1 và tam giác 3 (lớn nhất). Tam giác 3 giao với tam giác 2. Tam giác 4 không giao với tam giác nào khác. |
| 5 5 0 0 2 4 4 0 2 4 0 5 3 3 0 3 1 6 7 0 1 5 1 2 3 4 5 |
1 1 3 3 5 |
Hình vuông 1 có các đỉnh , , , ; hình vuông 2 chạm hình vuông 1 tại điểm , hai hình có cùng diện tích . Lục giác 4 (diện tích khoảng ) chạm hình vuông 1 tại và cắt tam giác 3 (diện tích khoảng ). Ngũ giác 5 không giao với đa giác nào khác. |
Bình luận