Svjetlost

Σε ένα επίπεδο, αν έχουμε ένα κυρτό πολύγωνο ~P~ , και τοποθετήσουμε μια πηγή φωτός σε ένα σημείο ~T~ που βρίσκεται έξω το πολύγωνο, ανάβουν μερικές πλευρές του ~P~ - αν η ~A~ και η ~B~ είναι δύο διαδοχικές κορυφές πολυγώνου, τότε το η πλευρά ~AB~ ανάβει εάν το εμβαδόν του τριγώνου ~ \bigtriangleup TAB~ δεν είναι μηδέν και αν δεν τέμνει στο εσωτερικό του το πολύγωνο. Η φωτεινότητα του πολυγώνου είναι το άθροισμα των μηκών των φωτιζόμενων άκρων και η μέγιστη φωτεινότητα ενός πολυγώνου είναι η μέγιστη δυνατή φωτεινότητα που μπορούμε να επιτύχουμε εάν επιλέξουμε ένα βέλτιστο σημείο ~T~ . Η απόσταση μεταξύ του σημείου ~T~ και του πολυγώνου μπορεί να είναι αυθαίρετη και οι συντεταγμένες του σημείου ~T~ δεν πρέπει απαραίτητα να είναι ακέραιοι.

Τα πολύγωνα ~P,\,P_1,\,P_2~ και ~P_3~ από το δεύτερο αρχείο ελέγχου, η βέλτιστη φωτεινότητα είναι σημειωμένη.

Σας δίνεται ένα κυρτό πολύγωνο ~P~ του οποίου οι κορυφές είναι, αντίστοιχα, τα σημεία ~A_1,\,A_2, \ldots,\,A_n~ .Το πολύγωνο αλλάζει σε ~q~ βήματα - στο ~j~-οστό βήμα, διαγράφουμε μια υπάρχουσα κορυφή πολυγώνου και λαμβάνουμε ένα νέο πολύγωνο ~P_j~ . Πιο συγκεκριμένα, οι κορυφές του πολυγώνου ~P_j~ είναι οι κορυφές του ~P~ που δεν έχουν διαγραφεί ακόμη και η σειρά είναι ίδια όπως στο πολύγωνο ~P~ . Είναι εύκολο να δούμε ότι κάθε πολύγωνο ~P_j~ είναι επίσης κυρτό.
Προσδιορίστε τη μέγιστη φωτεινότητα του πολυγώνου ~P~ και καθενός από τα ληφθέντα πολύγωνα ~P_1,\,P_2, \ldots,\,P_q~ .

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο ~n~ - τον αριθμό των κορυφών του αρχικού πολυγώνου ~P~. Η ~j~-οστή από τις ακόλουθες ~n~ γραμμές περιέχει δύο ακέραιους ~x_j~ και ~y_j~ ~(-10^9 \le x_j,\,y_j \le 10^9)~ - τις συντεταγμένες της κορυφής ~A_j~ . Η ακόλουθη γραμμή περιέχει τον ακέραιο ~q (0 \le q \le n - 3)~ - τον αριθμό των βημάτων. Η ~j~-οστή από τις παρακάτω ~q~ γραμμές περιέχει τον ακέραιο ~k_j (1 \le k_j \le n)~ που δηλώνει ότι στο ~j~-οστό βήμα διαγράφουμε την κορυφή ~A_{k_j}~ . Μπορείτε να υποθέσετε ότι οι κορυφές ~A_j~ στο πολύγωνο ~P~ δίνονται αριστερόστροφα, ότι δύο διαδοχικές παράλληλες γραμμές δεν υπάρχουν, και ότι όλοι οι δείκτες ~k_j~ είναι αμοιβαίως διαφορετικοί.

Έξοδος

Πρέπει να εκτυπώσετε ~q + 1~ γραμμές. Η πρώτη γραμμή πρέπει να περιέχει τη μέγιστη φωτεινότητα του αρχικού πολυγώνου ~P~ και η ~j~-οστή από τις ακόλουθες γραμμές ~q~ πρέπει να περιέχει τη μέγιστη φωτεινότητα του πολυγώνου ~P_j~ που προκύπτει μετά από ~j~ βήματα. Για κάθε γραμμή εξόδου, θα είναι μια απόλυτη και σχετική απόκλιση από την επίσημη λύση κατά ~10^{-5}~ ανεκτή.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	12	~n \le 100~
2	14	~n \le 2\,000~
3	14	~n \le 100\,000,\,q = 0~
4	29	~n \le 100\,000~, για κάθε ~j = 1, \ldots,\,q-1~ ισχύει ότι ~k_j < k_{j+1}~
5	31	~n \le 100\,000~

Παραδείγματα

input

4
0 0
10 0
10 10
0 10
1
2

output

20.000000
24.142136

input

6
2 2
4 0
6 0
8 2
8 4
2 4
3
1
4
3

output

10.828427
11.300563
10.944272
11.656854