#3038. H. Laser Alarm
-
ID: 3038
传统题
6000ms
512MiB
尝试: 0
已通过: 0
难度: (无)
上传者:
2000170131
H. Laser Alarm
Description
The museum in Byteland has plenty of jewels on display, secured by n laser alarms. Each laser alarmcan be considered as a segment in the 3D space. In this task, your job is to test the quality of the laser
alarm system. You need to find a plane such that it touches the most laser alarms. Note that if the plane
touches the endpoint of a segment, it should also be counted.
Input Format
The first line contains a single integer T (1 ≤ T ≤ 10), the number of test cases. For each test case:The first line contains a single integer n (1 ≤ n ≤ 50), denoting the number of laser alarms.
Each of the following n lines contains six integers xi, yi, zi, x′
i, y′
i and z′
i (1 ≤ xi, yi, zi, x′
i, y′
i, z′
i ≤ 100),
describing a segment that connects (xi, yi, zi) and (x′
i, y′
i, z′
i). It is guaranteed that the two endpoints of
each segment do not coincide.
Output Format
For each test case, output a single line containing an integer, denoting the maximum possible number oflaser alarms that can be touched
1
4
1 1 1 1 1 2
1 1 10 1 1 11
1 10 1 1 10 2
10 1 1 10 1 23