（双调欧几里得旅行商问题）在欧几里得旅行商问题中，给定平面上n个点作为输入，希望求出连接所有n个点的最短巡游路线。如下图，给出了一个7点问题的解，此问题是NP难问题，因此大家相信它并不存在多项式时间的求解算法。
J.L.Bentley建议将问题简化，限制巡游路线为双调巡游（bitonic tours），即从最左边的点开始，严格向右前进，直至最右边的点，然后掉头严格向左前进，直至回到起始点。下图给出了相同7个点的最短双调巡游路线。问题简化之后，存在一个多项式时间的算法。
设计一个O(n2)时间的最优双调巡游路线算法。你可以认为任何两个点的x坐标均不同，且所有实数运算都花费单位时间。（提示：有左至右扫描，对巡游路线的两个部分分别可能的最优解。）
