Maxim and Restaurant (Part 2)

Maxim and Restaurant (Part 1)

In previous post I discussed a O(n ^ 3 * k) solution. Today, I'm going to discuss how we can reduce the complexity to O(n ^ 2 * k). Basically if we see the problem from a different angle we don't need to run our DP for each blocker.

For n persons in queue, we have n! permutations. Lets consider the number of permutations for which we can allow only one person is p1, number of permutations for which we can allow two persons is p2, and so on.

So expected number of persons -
$e = \frac{p1 * 1 + p2 * 2 + ... pn * n}{n!}$

Which can be represented as -
$e = \frac{(p1 + p2 + ... + pn) + (p2 + p3 + ... + pn) + ... + (pn)}{n!}$

Here, p1 + p2 + ... + pn actually represents the number of ways where we can allow at least 1 persons. Lets call it m1. Similarly, p2 + p3 + .. + pn represents number of ways where we can allow at least 2 persons, which is m2 and so on.

So our equation is now -
$e = \frac{m1 + m2 + ... + mn}{n!}$
$=> e = \frac{m1}{n!} + \frac{m2}{n!} + \frac{m2}{n!}$
$=> e = f1 + f2 + .. + fn$

Here, fi = probability of allowing at least i persons.

In last post, in our dynamic programming has states dp[i][j]. In dp[i][j], we calculated probability of having sum j by adding first i persons. For a given k, if we add up all dp[k][j] for all 1 <= j <= p, we'll find the probability of allowing at least k persons. So by removing the blocker and running the dynamic programming algorithm only once we can simply calculate f1, f2, .. fn, and by adding these values, we can get our result.

So here is the simplified code -

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int[] a = new int[n];
        int total = 0;
        for (int i = 0; i < n; ++i) {
            a[i] = in.readInt();
            total += a[i];
        }
        int p = in.readInt();
        if (total <= p) {
            out.printLine(n);
            return;
        }

        double res = 0.;
        double[][] dp = new double[n + 1][p + 1];
        dp[0][0] = 1.0;
        for (int i = 0; i < n; ++i) {
            int cur = a[i];
            for (int oldCount = n - 1; oldCount >= 0; --oldCount) {
                for (int oldSum = 0; oldSum + cur <= p; ++oldSum) {
                    dp[oldCount + 1][oldSum + cur] += dp[oldCount][oldSum] / (n - oldCount) * (oldCount + 1);
                }
            }
        }

        for (int count = 1; count <= n; ++count) {
            for (int size = 0; size <= p; ++size) {
                res += dp[count][size];
            }
        }
        out.printLine(res);
    }

Maxim and Restaurant (Part 1)

Today I am going to discuss about a problem from +Codeforces - Maxim and Restaurant.

Maxim has n(<=50) guests in a queue and his table length is p (<=50). Maxim cannot arrange guests if summation of width of guests is more than p. So he allows next person in the queue to enter the room if total summation doesn't exceed p. If by adding next person makes it more than p, Maxim just discards the rest of the queue and doesn't allow anyone else to enter. What is the expected number of guests Maxim will allow if all of his guests queued up in a random order?

Solution:
We can iterate over all guests and consider that guest as a blocker, that means, this person will block the rest of the queue and will make the sum more than p.

We will now calculate a function f(count, sum), for all  0<=count<=n-1 and 0<=sum<=p. Here f(count, sum) represents, probability of having summation "sum" by adding first "count" persons in the queue. We'll be calculating f, without using the "blocker".  For all values of count and sum, f(count, sum) will contribute to our result if after adding blocker it makes the sum more than p. i.e. sum + width(blocker) > p. If that condition is true, we'll add $ f(count, sum) \times \frac{1}{n - count} \times count $. Here f(count, sum) is the probability of having summation "sum" by first "count" person, (1 / (n - count)) is the probability of having the blocker as a next person and count is the number persons will enter for this kind of permutation.

Check my java solution to see below how I calculated f using dynamic programming. Here dp(i, j) represents f(i, j).

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int[] a = new int[n];
        int total = 0;
        for (int i = 0; i < n; ++i) {
            a[i] = in.readInt();
            total += a[i];
        }
        int p = in.readInt();
        if (total <= p) {
            out.printLine(n);
            return;
        }

        double res = 0.;
        for (int blocker = 0; blocker < n; ++blocker) {
            double[][] dp = new double[n][p + 1];
            dp[0][0] = 1.0;

            for (int i = 0; i < n; ++i) {
                if (i == blocker) continue;
                int cur = a[i];

                for (int oldCount = n - 2; oldCount >= 0; --oldCount) {
                    for (int oldSum = 0; oldSum + cur <= p; ++oldSum) {
                        dp[oldCount + 1][oldSum + cur] +=
                              dp[oldCount][oldSum] / (n - oldCount) * (oldCount + 1);

                    }
                }
            }

            for (int count = 0; count < n; ++count) {
                for (int size = 0; size <= p; ++size) {
                    if (size + a[blocker] <= p) continue;
                    res += (dp[count][size] * count) / (n - count);
                }
            }
        }
        out.printLine(res);
    }

Here, dp[oldCount + 1][oldSum + cur] += dp[oldCount][oldSum] / (n - oldCount) * (oldCount + 1); because, after having a permutation of oldCount I can add a new person in this permutation in (oldCount + 1) possible positions. So we're multiplying (oldCount + 1), and probability of being selected at (oldCount + 1)th person from (n - oldCount) person is 1 / (n - oldCount). So we're multiplying this also. All f(count, sum) can be counted in O(n * n * p). As we're iterating over all the blockers. So the overall algorithm will be O(n ^3 * p).

No can you think of a solution having complexity O(n ^ 2 * p). I'll try to explain that in next post.

Height to Area (UVA - 10522)

I'm not good at Geometry at all. Now I'm trying to learn geometry and want to become good at it. I'm using this list of geometry problems shared by Shahriar Rouf Nafi. Today I'm going to discuss about this problem - Height to Area. You are given 3 heights of a triangle, you have to find out the area of the triangle.


Now given 3 sides Ha, Hb and Hc. We have to calculate the area A.

If three sides are a, b and c we can have -

\[ A = \frac{1}{2} \times a \times Ha ........ (1) \] \[ A = \frac{1}{2} \times b \times Hb ........ (2) \] \[ A = \frac{1}{2} \times c \times Hc ........ (3) \]
Now from 1 and 2, we can get
\[ \frac{a}{b} = \frac{Hb}{Ha} ........ (4) \] \[ \frac{b}{c} = \frac{Hc}{Hb} ........ (5) \]
From (4) and (5)
\[ a : b : c = Hb \times Hc : Hc \times Ha : Ha \times Hb \] As Ha, Hb and Hc given, we got the ratio of a, b and c.

So there will be a k, for which
\[ a = k \times Hb \times Hc ...... (6) \] \[ b = k \times Hc \times Ha ...... (7) \] \[ c = k \times Ha \times Hb ...... (8) \]
If the angles are A, B and C. We know that -

\[ \cos C = \frac{a^2 + b^2 - c^2}{2 \times b \times c} = \frac{Hb^2 \times Hc^2 + Hc^2 \times Ha^2 + Ha^2 \times Hb^2}{2 \times Hb \times Hc^2 \times Ha} \]
So, \[ C = \cos^{-1} \frac{Hb^2 \times Hc^2 + Hc^2 \times Ha^2 + Ha^2 \times Hb^2}{2 \times Hb \times Hc^2 \times Ha} \]
Now, from sin rule
\[ Ha = b \times \sin C \] \[ So,  b = \frac{Ha} {\sin C} ...... (9) \]
From (7) and (9)  we get
\[ k = \frac{1} {Hc \times \sin C} \]
We know Ha, Hb, Hc, and k, so we can calculate the exact value of a, b and c. So we can calculate the area of triangle by the following formula -
\[ A = \sqrt{ \frac{s \times (s - a) \times (s - b) \times (s - c)} {2} }, where   s = \frac{a + b + c}{2} \] This was my solution.

While discussing my solution with Nafi, he gave me a much smarter solution, Here it is
Area
\[ A = \frac{1}{2} \times a \times Ha \] So \[ a = 2 \times \frac{A}{Ha} ... (1) \] Similarly, \[ b = 2 \times \frac{A}{Hb} ... (2) \] \[ c = 2 \times \frac{A}{Hc} ... (3) \] Now, \begin{align} s &= \frac{a + b + c}{2}\\ &= (\frac{A}{Ha} + \frac{A}{Hb} + \frac{A}{Hc}) \end{align} And, \[ A^2 = s \times (s - a) \times (s - b) \times (s - c) \] \[ A^2 = (\frac{A}{Ha} + \frac{A}{Hb} + \frac{A}{Hc}) \times (\frac{A}{Hb} + \frac{A}{Hc} - \frac{A}{Ha}) \times (\frac{A}{Hc} + \frac{A}{Ha} - \frac{A}{Hb}) \times (\frac{A}{Ha} + \frac{A}{Hb} - \frac{A}{Hc}) \] \[ \Rightarrow A^2 = A^4 \times (\frac{1}{Ha} + \frac{1}{Hb} + \frac{1}{Hc}) \times (\frac{1}{Hb} + \frac{1}{Hc} - \frac{1}{Ha}) \times (\frac{1}{Hc} + \frac{1}{Ha} - \frac{1}{Hb}) \times (\frac{1}{Ha} + \frac{1}{Hb} - \frac{1}{Hc}) \] \[ \Rightarrow A^2 = \frac{1}{(\frac{1}{Ha} + \frac{1}{Hb} + \frac{1}{Hc}) \times (\frac{1}{Hb} + \frac{1}{Hc} - \frac{1}{Ha}) \times (\frac{1}{Hc} + \frac{1}{Ha} - \frac{1}{Hb}) \times (\frac{1}{Ha} + \frac{1}{Hb} - \frac{1}{Hc})} \] \[ \Rightarrow A = \sqrt{\frac{1}{(\frac{1}{Ha} + \frac{1}{Hb} + \frac{1}{Hc}) \times (\frac{1}{Hb} + \frac{1}{Hc} - \frac{1}{Ha}) \times (\frac{1}{Hc} + \frac{1}{Ha} - \frac{1}{Hb}) \times (\frac{1}{Ha} + \frac{1}{Hb} - \frac{1}{Hc})}} \]
Much cleaner solution. Thanks Nafi.
           

Silly Sort (Spoj - 2277, UVa - 1016)

Today I'll discuss the problem Silly Sort from spoj, which is also in uva.

In this problem you have to sort an array of integers in ascending order. Quite familiar to you. But here you are only allowed to swap any two elements. And each swap has a cost which is the sum of those two elements. You have to sort the array in minimum cost.

Seems tricky, so let's brainstorm. At first we have to know which element will go to which place after the complete sort. We can easily calculate that by copying the array into another array and sorting that array. Let's say original array is a and sorted array is b. So b[i] will go to i^th place for each i, in other word i is the destination of b[i]. First thing comes to our mind is, in each swap we will ensure that at least one element will move to it's destination. This will ensure minimum number of swaps, but will it confirm the minimum cost?

Let's work with the first example -

3

3 2 1

Sorted array will be -

1 2 3

So If we want to ensure at least one element will go to it's destination in each swap, then we have to swap 1 and 3, and after that that is our sorted array, cost is 4, which is minimum cost. So it's working for this example.

Let's try with another example

3

3 1 2

If we swap 3 and 1, then 1 will go to it's destination and the array will become - {1, 3, 2}, now we have to swap 3 and 2, then it will be sorted. Cost is (3 + 1) + (3 + 2) = 9. But in first move if we swap 1 and 2, it will become {3, 2, 1} and then swapping 3 and 1 will make it sorted and the cost will be (1 + 2) + (3 + 1) = 7. So two different ordering causes two different costs. So what will be our strategy?

Let's work with 4th example given with the problem -

6 
8 4 5 3 2 7 

Sorted array will be -

2 3 4 5 7 8

So, 2 will go to 8's place, 3 will go to 4's place, etc. Let's draw these relations.

In the above image, it is seen that 2 will go to 8's place, 8 will go to 7's place, 7 will go to 2's place. These three formed a cycle, another cycle is 3 → 4 → 5 → 3. So every input can be decomposed into some cycles.

So, our next approach is solving each cycles independently and sum of the costs for all cycles is our result. But what is the cost of solving a cycle. We see If we swap 2 and 8 of 2 → 8 → 7 → 2 cycle. 2 will go to it's destination, and 7 → 8 → 7 will form a smaller cycle.

If we swap two elements in a cycle of length K > 1 such that at least 1 element of this cycle will go to it's destination. Then after the swap, it will be splited into two cycles, one with length K - 1 and another one with length 1. We don't need to do anything with the cycle of length 1 because the element is already in it's destination.

Now for solving a cycle optimally, we need some observations -
1. Every element of this cycle will participate in at least 1 swap.
2. We need K - 1 swaps to sort this cycle. Each swap will add two elements to the cost. So 2 × (K - 1) elements will be added to the cost. There are K elements. So some elements will be added multiple times.

So if we want to move an element x to it's destination by swapping with another value, we should try to swap with the minimum value of that cycle. If we can do that for every element other than the smallest element. Than in the final cost, every element will be added once and the minimum element will be added K - 1 times. And we cannot make any less cost by confirming (1) and (2).  So this is the optimal approach to solve a cycle.

So In the above cycle 2 → 8 → 7 → 2, we'll swap 7 and 2 first. Cost is 9, then 8 and 2, cost is 10. So total cost is 19 for this cycle. In the same way, solving the second cycle 3 → 4 → 5 → 3 will cost 15. Total cost for this case is 34. This is the result of that example also.

Now let's try example 3 -

5 
1 8 9 7 6 

There are two cycles.

1 → 1

6 → 8 → 7 → 9 → 6

Solving the first cycle costs 0, and second cycle costs 42, total 42. But result is 41. So solving every cycles independently will not give the best result. Here in this example, the minimum element is 6 in the second cycle. As the cycle length is 4 it will be added 3 times which will cost 18. But if know there is an 1 in another cycle. We can borrow it by swapping with 6, which will cost 6 + 1 = 7, then do the sorting this time we use 1 instead of 6, this will add 3 instead of 18. After sorting 1 will be in place of 6's destination and we have to give the 1 back to it's own cycle and bring our 6 back. We can do it by one more swap which will cost another 7. So total cost 7 + 3 + 7 = 17 which is 1 less than 18. That's how the result is 41. So we'll try to borrow the minimum value of the whole given array and see whether it gives the optimal results or not.

Here is my simple solution in c++.

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>

using namespace std;

int a[100000];
int b[100000];
bool vis[100000];

int main (void) {
    int N;
    int t = 0;
    while (scanf("%d", &N) && N) {
        t++;
        for (int i = 0; i < N; ++i) {
            scanf("%d", &a[i]);
            b[i] = a[i];
            vis[i] = false;
        }
        sort(b, b + N);

        // Map the numbers to their desired place after sort
        map<int, int> place;
        
        for (int i = 0; i < N; ++i) {
            place[b[i]] = i;
        }
    
        int res = 0;
        for (int i = 0; i < N; ++i) {
            if (vis[i] == false) {
                if (place[a[i]] == i) {
                    vis[i] = true;
                    continue;
                }
                // We're in new cycle
                int min_val = a[i];
                int num = 0;
                int sum = 0;
                int j = i;

                while (vis[j] == false) {
                    sum += a[j];
                    num++;
                    if (a[j] < min_val) {
                        min_val = a[j];
                    }
                    vis[j] = true;
                    j = place[a[j]];
                }
                sum -= min_val;
                res += sum + min_val * (num - 1);
                
                // Let's try to borrow the minimum value.
                // If it's less costly then update our result.
                if (2 * (b[0] + min_val) <
                    (min_val - b[0]) * (num - 1)) {
                    res -= (min_val - b[0]) * (num - 1) -
                           2 * (b[0] + min_val);
                }    
            }
        }
        printf("Case %d: %d\n\n", t, res);
    }
    return 0;
}

SGU - 101 - Domino

This is another interesting problem.

Problem link : http://acm.sgu.ru/problem.php?contest=0&problem=101

Problem summery: You're given N (N <= 100) dominoes. Each of the dominoes has two numbers on it between 0 to 6, one in left side and another in right side. You have to arrange all the dominoes in a row so that they touch through equal marked side. If not possible print "No solution". Note that, we also have to check the graph is connected.

For example, we have three dominoes [1 2], [3, 2], [3 4]
If we arrange these dominoes like this -
[1 2] - [3 2] - [3, 4], this is invalid, because right side of first domino and left side of second domino marked with different numbers. But if we flip the second domino, to change left and right side, it will become -
[1 2] - [2 3] - [3 4], now every two adjacent dominoes touches with equal marked side. So it's a valid arrangement. So to organize it like this, we are allowed to rearrange dominoes and rotate any domino.

To solve this problem, we cannot try all possible arrangements because number of arrangements is too large. As the dominoes are marked with numbers between 0 to 6, we can consider we have a graph of 7 nodes named 0 to 6. If there is a domino [a b], we will consider there is an edge between a and b. Now we have a graph of at most 7 nodes and at most 100 edges. Our problem can be described as - is it possible to start traversing from one node and visit each of the edges exactly once?

Let's use the example from the problem. We have 5 dominoes [1 2], [2 4], [2 4], [6 4], [2 1]. We can build our graph like this -



And what about the solution? See the following image, yes we can traverse all edges exactly once.


The path we traversed is 4 -> 2 -> 1 -> 2 -> 4 -> 6. So, our domino arrangement will be, [4 2] - [2 1] - [1 2] - [2 4] - [4 6], if we write the indices of the dominoes this sequence is 2, 5, 1, 3, 4. Note that we flipped one [2 4] tile to [4 2] and [6 4] tile to [4 6]. We also need to output which domino we used as it is by a '+' sign, and which domino we flipped by a '-' sign. So our answer is -
2 -
5 +
1 +
3 +
4 -
Which is also given in the sample output.

Leonhard Euler proved that, we can visit every edge exactly once in a graph if number of nodes having odd degree is not more than two. If number of odd degree in the graph is two, we have to start from one of them and end our tour in another of them. By the name of Euler, this path is called Eulerian trail or Eulerian walk. For example in our graph in the image above, node 4 and 6 have odd degree, so we started at 4 and ended at 6.

So, if the number of odd degree of the graph is more than two, we will output "No solution", otherwise we will try to print any one of the solution, by finding out the Eulerian walk. But, what will be the strategy of our Eulerian walk. We can use the strategy of Fleury's algorithm. The strategy is, start with an odd degree node if there exists any, otherwise start with any node. At each iteration we visit the edge whose deletion would not disconnect the graph.

Now, as we have n edge, so we will remove one edge at each step of our algorithm. We'll try 7 different edges and after removing that edge we'll check whether the graph is connected nor not using a dfs, in our case, which is O(n). So our algorithm is somewhat like O(n * n).

My simple C++ solution -

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

bool vis[7];
vector<int> edge_index[7][7];
int degree[7];

// can reach v from u?
bool dfs(int u, int v) {
    if (u == v) {
        return true;
    }
    vis[u] = true;
    for (int i = 0; i <= 6; ++i) {
        if ((edge_index[u][i].size() > 0 || edge_index[i][u].size() > 0)
                && vis[i] == false) {
            if (dfs(i, v)) {
                return true;
            }
        }
    }
    return false;
}

bool is_connected() {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i <= 6; ++i) {
        if (degree[i]) {
            dfs(i, -1);
            break;
        }
    }    
    for (int i = 0; i <= 6; ++i) {
        if (degree[i] > 0 && vis[i] == false) {
            return false;
        }
    }
    return true;
}

int main (void) {
    int n; // number of dominoes i.e. number of edges
    scanf("%d", &n);
    memset(degree, 0, sizeof(degree));
    for (int i = 0; i <= 6; ++i) {
        for (int j = 0; j <= 6; ++j) {
            edge_index[i][j].clear();
        }
    }
    for (int i = 1; i <= n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        edge_index[u][v].push_back(i);
        degree[u]++;
        degree[v]++;
    }

    int n_odd = 0; // number of nodes with odd degree
    for (int i = 0; i <= 6; ++i) {
        if (degree[i] % 2 == 1) {
            n_odd++;
        }
    }

    if (n_odd > 2 || is_connected() == false) {
        // if number of odd degree node is more than 2
        // eulerian path doesn't exist for this graph
        printf("No solution\n");
    } else {
        int u = -1; // starting node

        // start node with an odd degree node, if exists
        for (int i = 0; i <= 6; ++i) {
            if (degree[i] % 2 == 1) {
                u = i;
                break;
            }
        }

        // if odd degree node not found, start with a node
        // with positive degree, i.e. start with any vertex,
        // which is used in the graph
        if (u == -1) {
            for (int i = 0; i <= 6; ++i) {
                if (degree[i] > 0) {
                    u = i;
                    break;
                }
            }
        }

        // Fleury's algorithm
        // n steps - at each step, remove one edge
        for (int i = 0; i < n; ++i) {
            int selected_ind;
            bool forward_selected;
            for (int j = 0; j <= 6; ++j) {
                if (edge_index[u][j].size() > 0 ||
                    edge_index[j][u].size() > 0) {
                    int cur_ind;
                    bool forward;
                    if (edge_index[u][j].size() > 0) {
                        cur_ind = edge_index[u][j].back();
                        edge_index[u][j].pop_back();
                        forward = true;
                    } else {
                        cur_ind = edge_index[j][u].back();
                        edge_index[j][u].pop_back();
                        forward = false;
                    }
                    degree[u]--;
                    degree[j]--;

                    memset(vis, 0, sizeof(vis));    
                    if (degree[u] == 0 || dfs(u, j) == true) {
                        // remove this edge
                        selected_ind = cur_ind;
                        forward_selected = forward;
                        u = j; // so we are in j now.
                        break;
                    } else {
                        // this edge cannot be removed
                        // back to previous state
                        if (forward) {
                            edge_index[u][j].push_back(cur_ind);
                        } else {
                            edge_index[j][u].push_back(cur_ind);
                        }
                        degree[u]++;
                        degree[j]++;
                    }
                }
            }
            printf("%d %c\n", selected_ind, forward_selected ? '+' : '-');
        }
    }

    return 0;
}

Maximum Triangle Area (Part 3 and final)

Part 1
Part 2

After second part, our algorithm became something like this -
for each 0 <= i < n, initialize A = P_i, B = P_{(i + 1) % n}, C = P_{(i + 2) % n}, then move C counter clockwise until area non-decreasing, move B to its adjacent point counter clockwise, if area non-decreasing, move C again until area non decreasing and so on. You will get the maximum area for each A and output the maximum of these areas. For a given point starting point P_i, if the maximum area is ABC. We can say ABC is 'stable' triangle for A, in other word s(p_i, P_{i + 1}, P_{i + 2}) = ABC, that means we cannot move B or C any further by not decreasing the area.

Now, after getting a maximum ABC for a fixed first point P_i, we will start with P_{i + 1}, P_{i + 2} and P_{i + 3}. We get A'B'C' as a stable triangle i.e. s(p_i, p_{i + 1}, p_{i + 2}) = A'B'C'. Hence our algorithm is O(n ^ 2). But it can be proved that, rather than, start from P_{i + 1} as a second point and P_{i + 2} as a third point, we can start with B and C as a second and third point and get the same result, i.e. s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C), where s(P_i, P_{i + 1}, P_{i + 2}) = ABC.

Lets assume that we are wrong, and s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = A'B'C' > s(p_i, P_{i + 1}, P_{i + 2}).

Case 1:
B' < B and C' = C


We know that,
ABC >= AB'C (otherwise largest triangle for A would be AB'C)
=> ABC + BB'A >= AB'C + BB'A
=> AB'BC >= AB'C + BB'A
=> AB'C + BB'C >= AB'C + BB'A
=> BB'C >= BB'A
=> BB'C >= BB'A' (for base BB' area is non decreasing from BB'C to BB'A, so it
will be non decreasing from BB'A to BB'C)
=> BB'C + A'B'C >= BB'A' + A'B'C
=> A'B'BC >= BB'A' + A'B'C
=> A'BC + BB'A' >= BB'A' + A'B'C
=> A'BC >= A'B'C
=> A'BC >= A'B'C' ...... [1] (as C = C')

So, for case 1, s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C).

Case 2:
Let's say, A'B'C' is the largest triangle for first point A'.
Where, B' < B and C' > C. See the following image.



For first point A, ABC is the largest trianlge,
So, ABC >= AB'C
=> ABC + BB'C >= ABC + BB'C
=> ABC + BB'C >= AB'BC
=> ABC + BB'C >= ABC + BB'A
=> BB'C >= BB'A
i.e. BB'A <= BB'C Hence, BB'A <= BB'C' (otherwise, BB'A > BB'C and BB'A <= BB'C, which is not possible for a convex polygon) So, BB'A' <= BB'C' ... [2] (as the triangle area non increasing by moving C' to A, it will be non increasing from A to A') Now as we are considering, for first point A', the largest area triangle is A'B'C'. So, A'B'C' > A'BC'
=> A'B'C' + BB'A' > A'BC' + BB'A
=> A'B'C' + BB'A' > A'B'BC'
=> A'B'C' + BB'A' > A'B'C' + BB'C'
=> BB'A' > BB'C', this contradicts to [2].

So it is not possible to have, A'B'C' > A'BC' i.e. for case 2, s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C).

Case 3:
Let's say, A'B'C' is the largest triangle for fixed first point A', where,
B' < B and C' < C

As ABC is the largest triangle having first point A,
either ABC' >= AB'C' (by moving B' to B, area increases) .. (3A)
or AB'C >= AB'C' (by moving C' to C, area increases) .. (3B)

Case 3A
ABC' >= AB'C'
=> ABC' + BB'A >= AB'C' + BB'A
=> AB'BC' >= AB'C' + BB'A
=> AB'C' + BB'C' >= AB'C' + BB'A
=> BB'C' >= BB'A
=> BB'C' >= BB'A' (As by moving C' to A area non increasing, moving A to A' will area be non increasing)
=> BB'C + A'B'C' >= BB'A' + A'B'C'
=> BB'A'C' >= BB'A' + A'B'C'
=> BB'A' + A'BC' >= BB'A' + A'B'C'
=> A'BC >= A'B'C'

So it is not possible to have, A'B'C' > A'BC' i.e. for case 3A, s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C).

Case 3B
AB'C >= AB'C'
=> AB'C + CC'B' >= AB'C' + CC'B'
=> AB'C'C >= AB'C' + CC'B'
=> AB'C' + CC'A >= AB'C' + CC'B'
=> CC'A >= CC'B'
=> CC'A' >= CC'B' (As moving A to B', area decreases, it's not possible moving A' to B' area increases)
=> CC'A' + A'B'C' >= CC'B' + A'B'C'
=> A'B'C'C >= CC'B' + A'B'C'
=> CC'B' + A'B'C >= CC'B' + A'B'C'
=> A'B'C >= A'B'C'

So it is not possible to have, A'B'C' > A'B'C i.e. for case 3B, s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C).

Case 4:
C' < C and B' = B

Here,
ABC >= ABC'
=> ABC + CC'A >= ABC' + CC'A
=> ABC + CC'A >= ABC'C
=> ABC + CC'A >= ABC + CC'B
=> CC'A >= CC'B
=> CC'A' >= CC'B
=> CC'A' + A'BC' >= CC'B + A'BC'
=> A'BC'C >= CC'B + A'BC'
=> A'BC + CC'B >= CC'B + A'BC'
=> A'BC >= A'BC'
=> A'BC >= A'B'C' (as B' = B)

So it is not possible to have, A'B'C' > A'BC i.e. for case 3B, s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C).

Case 5:
B' > B and C' < C


Now,
A'BC >= A'BC' (From case 4)
=> A'BC + CC'B >= A'BC' + CC'B
=> A'BC'C >= A'BC' + CC'B
=> A'BC' + CC'A' >= A'BC' + CC'B
=> CC'A' >= CC'B
=> CC'A' >= CC'B'
=> CC'A' + A'B'C' >= CC'B' + A'B'C'
=> CC'B'A' >= CC'B' + A'B'C'
=> CC'B' + A'B'C >= CC'B' + A'B'C'
=> A'B'C >= A'B'C'

So it is not possible to have, A'B'C' > A'B'C i.e. for case 5, s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C).

So, from all of the 5 possible cases, we found that, s(P_{i + 1}, P_{i + 2}, P_{i + 3}) = s(P_{i + 1}, B, C). So our algorithm will still work, if we start our iteration for first point i = i + 1, without changing the position 2nd and 3rd point. We will move first point from 0 to n - 1, and 2nd and 3rd point will also not move more than n times. So our algorithm in worst case is O (3 * n) = O(n)

My simple implementation in C++.

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<cassert>
#include<sstream>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;

struct Point {
    int x;
    int y;
    Point(int _x, int _y) : x(_x), y(_y) {}
    Point() : x(0), y(0) {}
    bool operator <(const Point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
};

bool left_turn(const Point& p1, const Point& p2, const Point& p3) {
    return (p2.y - p1.y) * (p3.x - p1.x) - (p2.x - p1.x) * (p3.y - p1.y) > 0;
}

// Returns list of points of convex hull in counter clockwise
// The last point and first point will be equal
vector<Point> convex_hull(vector<Point> p) {
    vector<Point> ret;
    sort(p.begin(), p.end());
    // build lower hull
    for (int i = 0; i < p.size(); ++i) {
        while (ret.size() >= 2 &&
               left_turn(ret[ret.size() - 2], ret[ret.size() - 1], p[i])) {
            ret.pop_back();
        }
        ret.push_back(p[i]);
    }
    int lower_hull_size = ret.size();
    // build upper hull
    for (int i = p.size() - 2; i >= 0; --i) {
        while (ret.size() - lower_hull_size >= 1 &&
               left_turn(ret[ret.size() - 2], ret[ret.size() - 1], p[i])) {
            ret.pop_back();
        }
        ret.push_back(p[i]);
    }
    return ret;
}

double triangle_area (const Point& p1, const Point& p2, const Point& p3) {
    return abs((double) p1.x * p2.y +
               (double) p2.x * p3.y +
               (double) p3.x * p1.y -
               (double) p1.y * p2.x -
               (double) p2.y * p3.x -
               (double) p3.y * p1.x) / 2.0;
}

int main (void)
{
    int n;
    while (scanf("%d", &n) && n != -1) {
        vector<Point> p;
        for (int i = 0; i < n; ++i) {
            int x, y;
            scanf("%d%d", &x, &y);
            p.push_back(Point(x, y));
        }
        p = convex_hull(p); p.pop_back();
        int i = 0;
        int j = i + 1;
        int k = j + 1;
        double res = 0.;
        while (true) {
            double area = triangle_area(p[i], p[j], p[k]);
            while (true) {
                while (true) {
                    int nk = (k + 1) % n;
                    double narea = triangle_area(p[i], p[j], p[nk]);
                    if (narea >= area) {
                        k = nk;
                        area = narea;
                    } else {
                        break;
                    }
                }
                int nj = (j + 1) % n;
                double narea = triangle_area(p[i], p[nj], p[k]);
                if (narea >= area) {
                    j = nj;
                    area = narea;
                } else {
                    break;
                }
            }
            if (area > res) res = area;
            i++;
            if (i == j) j = (j + 1) % n;
            if (j == k) k = (k + 1) % n;
            if (i == n) break;
        }
        printf("%.2lf\n", res);
    }
    return 0;
}