trang chủ / đề bài / icpc26_mn_j

Phosphorus nghiên cứu đa giác

Đề bài

Mô tả

Phosphorus đã vẽ n đa giác đều trên mặt phẳng tọa độ Descartes. Các đa giác được đánh số từ 1 đến n.

Mỗi đa giác đều thứ i được mô tả bởi tọa độ tâm (xi,yi), khoảng cách từ tâm đến các đỉnh ri (bán kính đường tròn ngoại tiếp) và số cạnh ki. Để tránh nhập nhằng về góc xoay, giả sử luôn có một đỉnh của đa giác thứ i nằm đúng tại (xi,yi+ri), ki−1 đỉ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à 10−3. Ở đâ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 0.

Phosphorus sẽ đưa ra q truy vấn. Mỗi truy vấn gồm một số nguyên u (1≤u≤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ứ u. Trong số các đa giác đó, hãy tìm chỉ số j (1≤j≤n) 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ó k cạnh và bán kính đường tròn ngoại tiếp r được tính theo công thức Diện tích=12kr2sin(2πk). Đảm bảo rằng khi hai đa giác có cặp (ki,ri) khác nhau thì diện tích lớn hơn gấp ít nhất (1+10−12) 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 n và q (1≤n,q≤3·105): số đa giác và số truy vấn.
  • n dòng tiếp theo, mỗi dòng chứa bốn số nguyên xi, yi, ri và ki (−106≤xi,yi≤106, 1≤ri≤106, 3≤ki≤7): 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ứ i.
  • q dòng tiếp theo, mỗi dòng chứa một số nguyên u (1≤u≤n): chỉ số của đa giác trong truy vấn hiện tại.

Dữ liệu ra

In ra q dòng. Với truy vấn thứ m, in ra một số nguyên j: 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 u. Nếu có nhiều đa giác giao với u 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

  • 1≤n,q≤3·105.
  • −106≤xi,yi≤106, 1≤ri≤106, 3≤ki≤7.
  • 1≤u≤n.
  • Hai đa giác không giao nhau thì cách nhau ít nhất 10−3.
  • Hai đa giác có cặp (ki,ri) khác nhau thì tỉ số diện tích (lớn chia nhỏ) ít nhất là 1+10−12.

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 (0,2), (−2,0), (0,−2), (2,0); hình vuông 2 chạm hình vuông 1 tại điểm (2,0), hai hình có cùng diện tích 8. Lục giác 4 (diện tích khoảng 2,6) chạm hình vuông 1 tại (0,2) và cắt tam giác 3 (diện tích khoảng 11,7). Ngũ giác 5 không giao với đa giác nào khác.

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