Solution of round #180 Div 1 Problem E -- Mystic carvings

For any three lines, they can intersect in one of the following 5 ways:

The problem is asking for the number of Type 2 or Type 5. Some of these configs are easy to count (e.g. Type 1), some are not. To count the number of Type 1, we can exhaust the middle line with index i, and count the number of lines on the right of the middle line (let it be x_i) and on the left of the middle line (let it be y_i), then the number of Type 1 with that middle line is given by x_iy_i. There are several methods to calculate x_i efficiently. One of them is to process the endpoints in counter clockwise order (let the current endpoint be k), and use a segment tree or binary indexed tree to keep track of the number of lines (a_i, b_i), a_i < b_i with l ≤ a_i < b_i ≤ k for different l. Let j be the line with b_j = k, then to find the number of lines with a_j < a_i < b_i < b_j, we just need to query the count at a_j, then update the binary indexed tree by adding one to the position a_j. In the actual implementation, we need to consider that the endpoints are wrapped circularly as well.

Unfortunately, Type 2 and Type 5 are the difficult ones. But we are only asked to find the total number of Type 2 and Type 5, which is (number of triples of lines) — (number of Type 1, 3 and 4). The problem then reduces to finding the total number of Type 3 and 4 (namely "We cannot give a 囧 without an XD and a HA"). Note that Type 3 and 4 shares a characteristic that two of the lines (the X in Type 3, and the two vertical lines in Type 4) has exactly one intersection with one of the other two lines. Therefore we can find the number of Type 3 and 4 by iterating through the lines, then count the number of lines on the right (x_i), on the left (y_i), and intersecting the considered line (z_i = n - 1 - x_i - y_i), and give the number of Type 3 and 4 as the sum of z_i(x_i + y_i). After removing double counting, we can get the answer.