Counting the number of valid isosceles trapezoids that can be formed from sticks Let's say I have $n$ sticks with length $l_1\leq l_2 \leq l_3 \leq ... \leq l_n, n\geq 4$. (The lengths are positive integers.)
I want to count the number of different sets of four sticks that can form an isosceles trapezoid. (Note that if there are two sticks that are equal, we treat them as two different sticks). 
The naive the solution that comes to mind is a $O(n^4)$ solution to check all possible sets and see if they form a valid isosceles trapezoid (By checking the height and seeing if its $>0$). However, I am looking for something better, any idea?
 A: Some observations:


*

*The number of equal sticks in any valid set must be at least 2, at most 3.

*Four equal sticks will never be valid.

*Two pairs of equal sticks will never be valid.

*Four sticks all of different lengths (unequal) will never be valid.

*For a set to be valid, the sum of two identical sticks in it must be strictly greater than the difference between the other two sticks.


This allows for a lot of optimizations.  From the original sequence (which should be sorted with some variation of counting sort or bucket sort), choose two identical items.  Count the ways to choose two other elements distinct from each other (but not necessarily from the two identical elements already chosen).  Constrain this selection to items whose difference is strictly less than the sum of the identical items already chosen.  Multiply along the way by the number of ways to choose identical items.

So for the sequence:
1 2 3 3 6 7 7 7 10 10 14 14 14 14 14 20 24 24 37 40 40 40 40 40 50 50 50 67

Summarized as:
1 2 3 6 7 10 14 20 24 37 40 50 67
    2   3  2  5     2     5  3

The valid sets can be counted:
choose both 3s - sum is 6.  (Can't choose 1 with anything greater than 6.)
  pair (1 2) count 1
  pair (2 7) x 3
  (6 7) x 3
  (6 10) x 2
  (7 10) x 3 x 2
  (10 14) x 10
  (20 24) x 2
  (37 40) x 5
  = 1+3+3+2+6+10+2+5 = 32 for the pair of 3s
choose two 7s (3 ways to do this except when we choose the third 7 also)
  sum is 14
  1 pairs up with anything up to and including 14
  1: 11 x 3 + 1 = 34 sets that include a 1 and at least two 7s
  ...

There are probably much cleaner ways to do this, but this is a relatively straightforward method of counting, and you don't have to choose every possible set of 4 sticks.
