Hướng dẫn cho A problem with a sussy content

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: flo

Lưu ý

Bài này sử dụng hầu như là kiến thức toán lớp $9$ nên sẽ khá khó hiểu với những bạn đang học từ lớp $8$ trở xuống. Nên cân nhắc trước khi đọc hướng dẫn.

Subtask 1: $1 \le n \le 2 \times 10^3$ .

Hint

Để khoảng cách từ $O$ đến một đường thẳng bất kỳ ngắn nhất thì $O$ phải nằm trên một đường thẳng vuông góc với đường thẳng trên.

Hướng tiếp cận

Ta duyệt qua các cặp điểm. Với mỗi cặp, ta sẽ xác định vị trí giao nhau của đường thẳng cắt $2$ điểm đó và đường thẳng chứa điểm $O$ sao cho chúng vuông góc với nhau. Gọi giao điểm đó là $I$ , khi đó ta có thể tính $IO$ bằng định lý Cosines hoặc công thức Heron.
Sau khi duyệt xong, ta chỉ cần in ra kết quả thỏa mãn.
Độ phức tạp của ý tưởng trên là $O(\frac{N \times (N-1)}{2})$ .

Subtask 2: Không giới hạn gì thêm.

Hint

Cũng như subtask $1$ nhưng ta gọi $r$ là đáp án cần tìm. Khi đó $r$ lớn thứ $n$ thì phải có $\frac {n\times(n-1)}{2} -n+1$ giá trị $r$ lớn hơn $r$ .

Hướng tiếp cận

Ta gọi một đường tròn tâm $O$ với bán kính $r$ , gọi $2$ điểm $A, B$ nằm ở ngoài đường tròn. Ta có thể thấy rằng khoảng cách từ đường thẳng cắt $A, B$ đến $O$ sẽ lớn hơn $r$ . Ta sẽ chặt nhị phân trên các giá trị $r$ để đếm số cặp điểm $A, B$ sao cho thỏa mãn điều kiện trên như gợi ý, từ đó cũng có thể xác định được kết quả nhỏ nhất.
Để làm điều trên, ta sẽ gọi các tiếp tuyến từ $A, B$ và các điểm tương ứng trên đường tròn lần lượt là $A_1, A_2, B_1, B_2$ . Khi đó đoạn thẳng $A_1A_2$ và đoạn thẳng $B_1B_2$ sẽ giao nhau và đoạn thẳng $AB$ trên cũng sẽ không cắt đường tròn (chứng minh ở dưới) và ngược lại. Để tính $A_1A_2, B_1B_2$ , ta có thể sử dụng định lý Cosines.
Dựa vào những điều trên, ta sẽ tính số đoạn giao nhau của các đoạn thẳng tạo bởi các tiếp điểm tương ứng. Để kiểm tra $r$ có thỏa mãn, ta cần đếm số cặp điểm mà các đoạn thẳng của các đoạn thẳng tạo bởi các tiếp điểm tương ứng giao nhau. Để làm điều này, ta phải sắp xếp các điểm kết thúc của các đoạn và tạo một cây (Segment Tree hoặc Fenwick Tree đều được nhưng mình đề xuất Fenwick) để nén lại các tọa độ.
Việc còn lại là ta chỉ cần kiểm tra các điểm kết thúc của từng đoạn. Khi gặp điểm bắt đầu của một đoạn, ta lưu trữ đoạn đó trong cây cho đến khi gặp điểm kết thúc của đoạn đó. Điều này cho phép ta truy vấn lấy số lượng điểm lớn hơn điểm bắt đầu để tính.
Độ phức tạp của ý tưởng trên là $O(2 \times n \times log(n) \times log(10^6))$ với $log(n)$ là thời gian cập nhật các điểm của các đoạn.

Chứng minh

Tạm thời mình chưa chứng minh được

Bình luận

Không có bình luận nào.