Ciel and Map
All submissions for this problem are available.
Tomya is a girl. She loves Chef Ciel very much.
Tomya writes a tetragon (see the below Notes 1 for details) in her map.
The map has N points, whose coordinate are (Xi, Yi), denoting Ciel's restaurants.
Each vertex of the tetragon written by Tomya is one of the Ciel's restaurants.
Tomya doesn't show her tetragon in the map, but she says that she draws a long segment.
To guess her tetragon, please tell the maximum length of a segment which can be one of the sides in her tetragon. (See Notes 2 for the definition of length)
A tetragon means a polygon with 4 sides.
A tetragon must be simple, that is, the boundary of the tetragon does not cross itself.
A tetragon does not have to be convex.
The length of a segment is defined as the Euclidean distance between the endpoints.
That is, the length of the segment (x1, y1) - (x2, y2) is the square root of (x1 - x2)2 + (y1 - y2)2.
The first line contains an integer T, the number of test cases.
Then T test cases follow.
The first line of each test case contains an integers N.
Then next N lines follow.
The i-th line contains 2 integers denoting Xi and Yi.
For each test case, print the maximum length of a segment which can be one of sides in her tetragon.
This value must have an absolute error no more than 0.000001 (10-6).
1 ≤ T ≤ 1250
4 ≤ N ≤ 1000
1 ≤ Xi, Yi ≤ 5000
The sum of N in one test file does not exceed 5000.
No three points (Xi, Yi), (Xj, Yj), (Xk, Yk) lie in the same line (1 ≤ i < j < k ≤ N)
1 6 3 1 5 2 3 3 6 3 6 6 5 6
The below figure denotes one of the valid tetragons for the sample input.
The red segment is the longest segment which can be one of the sides in her tetragon.
|Tags||cook24, easy, geometry, laycurse|
|Time Limit:||0.367347 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, ADA, CAML, ASM, CLPS, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, ERL, TCL|
Fetching successful submissions
If you are still having problems, see a sample solution here.