Ear

Problem Statement

There are some red points and blue points on the Cartesian plane. All red points are on the x-axis and all blue points are in the upper half-plane. That is, the y-coordinate of each red point is 0, and the y-coordinate of each blue point is strictly positive.

Fox Ciel wants to form an ear-shaped figure using these points. She defines that the pair of four different red points A, B, C, D and two blue points P, Q is called an ear if and only if all the following conditions are satisfied.

• Both points B and C lie strictly inside the segment AD.
• The angles PAD, PDA, QBC and QCB are strictly less than 90 degrees.
• Point Q is strictly inside of the triangle PAD.

In the following image, points in the left figure form an ear while points in the right figure do not.

You are given three String[]s redX, blueX and blueY. Concatenate all elements of redX to get a space-separate list of integers. The i-th integer of this list represents the x-coordinate of i-th red point. In the same way, blueX and blueY encode lists of x-coordinates and y-coordinates of blue points.

Your method must return the number of ways in which we can choose the four red and two blue points that form an ear.

Definition

Class:

Ear

Method:

getCount

Parameters:

String[], String[], String[]

Returns:

long

Method signature:

long getCount(String[] redX, String[] blueX, String[] blueY)

(be sure your method is public)

Notes

• The order of points in an ear does not matter. I.e., if two ears have the same four red and two blue points, they are considered the same.

Constraints

• redX, blueX and blueY will each contain between 1 and 50 elements, inclusive.
• Each element of redX, blueX and blueY will contain between 1 and 50 characters, inclusive.
• After concatenating the elements of redX, the resulting string will be a single space separated list of integers.
• After concatenating the elements of blueX, the resulting string will be a single space separated list of integers.
• After concatenating the elements of blueY, the resulting string will be a single space separated list of integers.
• There will be between 1 and 300 integers in each of the lists.
• The number of integers in the lists of blueX and blueY will be the same.
• Each integer in the lists will be between 1 and 10,000, inclusive.
• All the integers in each list will be distinct.
• Integers in the lists will have no leading zeros.

Examples

1. {"3 2 8 7"}

   {"5 4"}

   {"2 4"}

   Returns: 1

   This case corresponds to the left figure in the statement.

2. {"3 2 8 7"}

   {"2 8"}

   {"3 4"}

   Returns: 0

   This case corresponds to the right figure in the statement.

3. {"1 2 6 9"}

   {"3 6 8 5"}

   {"1 5 4 3"}

   Returns: 4

   There exists only one possible combinations of A, B, C and D since there are only four red points. Possible combinations of P and Q are as follows. {(5, 3), (3, 1)} {(6, 5), (3, 1)} {(8, 4), (3, 1)} {(6, 5), (5, 3)}

4. {"10000"}

   {"10000 9999"}

   {"10000 9999"}

   Returns: 0

   It is impossible to choose four red points from only one red point.

5. {"100 2", "00", " 39", "9", " 800 900 9", "99"}

   {"15", "0 250 ", "349"}

   {"2 3 1"}

   Returns: 12

   Concatenate each element of the String[]s correctly.

6. {"1", " ", "2", " ", "3", " ", "4 5 6", " 7 8 9"}

   {"4", " ", "5", " ", "6", " 7 ", "8"}

   {"1", " 2 ", "3 4", " 5"}

   Returns: 204