Optimal Subset

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Problem description.
You are given a convex polygon of n vertices P_{1}, P_{2}, ..., P_{n} (in counterclock or clock order). Each vertex is assigned with a weight w_{i}.
Find a subset of vertices that includes vertex 1.
1 = i_{1} < i_{2} < ... < i_{k} ≤ n that maximizes ratio:
(dist(i_{1}, i_{2}) + dist(i_{2}, i_{3}) + ... + dist(i_{k}, i_{1})) / (w_{i1} + w_{i2} + ... + w_{ik}).
Where dist(i, j) refers to Euclidean distance between two points P_{i}, P_{j}.
Input
The first line contains an integer T denotes the number of test cases. Each test case is describes as follow:
An integer n on a single line.
n next lines, each line contains two integers, that is coordinates of ith vertex
The last line contains n spaceseperated integer, denotes weight of vertex.
Output
Each testcase output the maximum ratio can reach on a single line.
Your answer will be considered correct if it has an absolute error less then 10^{6}.
Constraints
 1 ≤ T ≤ 10
 3 ≤ n ≤ 10^{5}
 The sum of n over all test cases is at most 2.10^{5}
 0 ≤ all coordinates ≤ 10^{9}
 1 ≤ w_{i} ≤ 10^{5}
Subtask:
 Subtask #1 (10 points): n ≤ 15
 Subtask #2 (30 points): n ≤ 1000
 Subtask #3 (60 points): original constrains
Example
Input: 3 3 0 0 1 5 2 9 4 4 20 4 0 0 1 5 2 7 3 6 12 15 12 11 5 0 0 1 5 2 8 3 9 4 8 12 11 18 2 7 Output: 1.274754878 0.606675824 1.355261854
Author:  chemthan 
Tester:  melfice 
Editorial  https://discuss.codechef.com/problems/OPTSSET 
Tags  chemthan, chemthan, ltime53, maths, mediumhard, optimization 
Date Added:  21092017 
Time Limit:  8 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 