The Cartesian Job

Có lẽ bạn đã nghe nói về khối trụ bạch kim–iridi dùng làm chuẩn kilôgam, nhưng bạn có biết còn có một đoạn thẳng đặc biệt dùng làm chuẩn kilômét không? Trong một địa điểm bí mật và rất bằng phẳng, đoạn thẳng ấy nằm trên mặt phẳng hai chiều, nối \((0,0)\) với \((0,1000)\).

Đương nhiên đoạn chuẩn này vô cùng quý giá, nên nó được bảo vệ bởi \(N\) laser giám sát quay, mỗi laser là một tia trên mặt phẳng. Mỗi laser có một đầu mút cố định và quay quanh đầu mút đó với tốc độ không đổi đúng một vòng mỗi giây. Hệ thống an ninh chọn chiều quay thuận hay ngược chiều kim đồng hồ của từng laser một cách độc lập và đồng xác suất.

Các laser không bị cản bởi laser khác, bởi đầu mút của chúng hay bởi chính đoạn chuẩn. Không laser nào có đầu mút nằm trên đoạn chuẩn.

Bạn được thuê để kiểm định hệ thống an ninh, nhưng dữ liệu duy nhất là một ảnh chụp tại một thời điểm, cho biết đầu mút và hướng của từng laser lúc ấy. Vì chỉ là ảnh tĩnh, bạn không thể suy ra chiều quay của bất kỳ laser nào.

Bạn xác định rằng đoạn chuẩn có thể bị đánh cắp nếu từng tồn tại một khoảng thời gian mở, khác rỗng mà không laser nào chạm vào đoạn. Xác suất để điều đó xảy ra là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số lượng test \(T\). Mỗi test bắt đầu bằng một dòng chứa số nguyên \(N\), là số laser. Tiếp theo là \(N\) dòng; dòng thứ \(i\) chứa bốn số nguyên \(X_i,Y_i,X'_i,Y'_i\), lần lượt là tọa độ đầu mút của tia laser thứ \(i\) và tọa độ của một điểm khác nằm trên tia đó.

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó x là số thứ tự test (bắt đầu từ 1), còn y là xác suất cần tìm. Kết quả được chấp nhận nếu sai số tuyệt đối hoặc tương đối không quá \(10^{-6}\).

Ràng buộc

• \(1\le T\le100\).
• \(-10^6\le X_i,Y_i,X'_i,Y'_i\le10^6\) với mọi \(i\).
• \((X_i,Y_i)\ne(X'_i,Y'_i)\) với mọi \(i\).
• Nếu \(X_i=0\) thì \(Y_i<0\) hoặc \(Y_i>1000\); tức là không đầu mút laser nào nằm trên đoạn chuẩn.

Phân nhóm

• Test Set 1 (hiển thị): \(1\le N\le10\).
• Test Set 2 (ẩn): \(1\le N\le10000\); có nhiều nhất 8 test với \(N>100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
5
0 1001 -1 1001
0 1001 -1 1001
0 1001 -2 1001
0 1001 0 500
0 1002 1234 5678
4
500 500 1000 1000
500 500 0 1000
500 500 0 0
500 500 1000 0
4
500 500 1000 1001
500 500 0 1000
500 500 0 0
500 500 1000 0

Case #1: 1.000000
Case #2: 0.750000
Case #3: 1.000000

Nguồn

Google Code Jam 2018, Chung kết thế giới, bài The Cartesian Job.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.