SRM 304

Idea Flow

Input Constraint ~  Given set of N points and we need to form convex polygon in order to                                                   maximize the area. 

Question Hints    ~  Solution of an triangle can be use for polygon.

Conclusion           ~  Different start points starting from n-1| 0 |1 and dp can be found.

Learnt lesson       ~  Geometric problem are easy, just need time to understand what they want.

Algorithm 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

best[0] = best[1] = 0; // Here I am moving the point 1. for(int i = 2 ; i < n ; i++) { best[i] = max(best[i - 1], best[i - 2] + sqrtIt(x[i], y[i], x[i-2], y[i-2])); } double res = best[n - 1]; // Now lets try moving the point 0. best[0] = 0; best[1] = sqrtIt(x[n-1], y[n-1], x[1], y[1]); best[2] = best[1]; for(int i = 3; i < n; i++ ) { best[i] = max(best[i - 1], best[i-2] + sqrtIt(x[i], y[i], x[i-2], y[i-2])); } res = max(best[n - 1], res); //Now moving point n - 1. best[0] = sqrtIt(x[n-2], y[n-2], x[0], y[0]); best[1] = best[0]; for(int i = 2 ; i < n - 1 ; i++) { best[i] = max(best[i - 1], best[i-2] + sqrtIt(x[i], y[i], x[i-2], y[i-2])); } res = max(best[n - 2], res);