Nhà du hành quả cảm K, có thể là tác giả bài này hoặc không, gần đây đi lại rất nhiều. Trong một chuyến đi, cô bay từ San Francisco tới Frankfurt, Johannesburg, Abu Dhabi, Singapore, Tokyo rồi trở về San Francisco. Cô đã đi vòng quanh Trái Đất theo một đường khép kín chạm mọi kinh tuyến: với mỗi kinh độ có thể có, đường đi có ít nhất một điểm ở kinh độ đó.

Tuy nhiên, K không chắc chuyến ấy đủ “siêu tuyệt vời”, vì người ta cũng có thể đi vòng quanh Trái Đất bằng cách bay tới Bắc Cực rồi đi bộ một vòng quanh đó; ngoài việc bay tới Bắc Cực, việc này không có vẻ khó. Vì vậy cô đưa ra khái niệm tổng quát hơn: omnicircumnavigation — một đường khép kín quanh Trái Đất, coi Trái Đất là mặt cầu, vẫn là một hành trình vòng quanh bất kể đặt hai cực ở đâu. Nói cách khác, đó là đường khép kín trên mặt cầu chạm mọi bán cầu có thể chọn; chạm biên bán cầu là đủ. Tương đương, đường ấy cắt mọi đại vòng, tức mọi đường tròn có đường kính lớn nhất trên mặt cầu.

Bạn được cho một dãy \(N\) điểm trên mặt cầu bán kính 1. Hãy kiểm tra đường nối chúng theo thứ tự có phải omnicircumnavigation hay không. Đường đi nối mỗi cặp điểm liên tiếp bằng tuyến ngắn nhất trên bề mặt, rồi nối điểm cuối về điểm đầu theo cùng cách. Không có hai điểm liên tiếp nào, kể cả cặp cuối–đầu, thẳng hàng với gốc tọa độ: chúng không đối cực và cũng không phải cùng một điểm trên mặt cầu.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng \(N\), số thành phố K ghé thăm. \(N\) dòng sau chứa ba số nguyên \(X_i,Y_i,Z_i\). Điểm thứ \(i\) trên mặt cầu có tọa độ

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test và y là YES nếu hành trình là omnicircumnavigation, ngược lại là NO.

Ràng buộc

• \(1\le T\le200\).
• \(-10^6\le X_i,Y_i,Z_i\le10^6\) với mọi \(i\).
• Ít nhất một trong \(X_i,Y_i,Z_i\) khác 0 với mọi \(i\).
• Với mọi cặp liên tiếp \(i,j\), gồm cả \(i=N-1,j=0\), không vectơ nguyên nào trong hai vectơ \((X_i,Y_i,Z_i)\) và \((X_j,Y_j,Z_j)\) là bội nguyên của vectơ kia. Do đó hai điểm không trùng nhau và không đối cực trên mặt cầu.

Phân nhóm

Test Set 1 (Small, hiển thị)

\(3\le N\le50\).

Test Set 2 (Large, ẩn)

\(3\le N\le5000\).

Đ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ụ

4
3
1 0 0
0 1 0
0 0 1
8
5 5 5
5 -5 5
-5 -5 5
-5 5 5
-5 5 -5
-5 -5 -5
5 -5 -5
5 5 -5
3
1 0 0
-1 1 0
-1 -1 0
5
1 0 0
-1 1 0
2 0 0
-2 2 0
-1 -1 0

Case #1: NO
Case #2: YES
Case #3: YES
Case #4: YES

Nguồn

Google Code Jam 2017, Chung kết thế giới, bài Omnicircumnavigation.

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