2014
01-26

# Dividing Sea Area to Navigation-Triangle

When a vessel sails on the vast and boundless sea, the captain must know his position in any time. There is a technique called triangle-navigation can solves this problem.

Suppose there are three islands in some sea area. They form a large triangle. There is a radio navigation station respectively on each island. The navigation station sends out radio signals continuously. After the vessel receives the signals, its position can be known by calculating those three different signals.

There is a raised n-multilateral sea area which is formed by n islands. Each island has a radio navigation station. The n islands form a raised n-multilateral graph. Every three islands form a triangle division area. Vessels sailing in this triangle area should determine the position by the signals from those three radio navigation stations in the three islands.

Of course, all navigation triangles divided from the raised n-multilateral graph can not overlap one another. Consequently, this raised n-multilateral graph is divided into n-2 triangles areas.

By the way, there are some smaller islets in the raised n-multilateral sea area and there is no navigation station in any islet. These small islets are related with our problem, we will explain it later.

An experienced captain had navigated in this sea area for several years. However, he found it is improper to divide the sea area to n-2 navigation triangles as the current scheme. After deep thinking, he put forward a new method.

Of course, he still divided raised n-multilateral graph sea area into n-2 navigation triangles which are not overlapped one another. The three vertexes of the triangles are three islands with navigation station. According to the scheme which is put forward by the old captain, a weight value is necessary for each triangle sea division area. Calculating formula of the weight value is as follows:
V= S+2*a +b

In that formula, the letter “V” expresses the weight value of the triangle sea area, the letter “S” expresses the area of that triangle sea, The letter “a” expresses the number of smaller islets inside the triangle. The letter “b” expresses the number of those small islets on the common edge between the two triangle sea areas. After calculating according to the formula above, each triangle sea area division has a weight value. The old captain thought, for the n-2 triangle areas, there will be n-2 weight values. Among these weight values, when the difference of the maximum weight value and the minimum weight value reaches a minimum, this scheme of division is optimum. That scheme will benefit sailing most.
As none people can solve that problem on the vessel. Now the captain is visiting you, he hopes you can help him.

Two positive integers n (3<=n <=100) and m (0 <=m<=20) are provided firstly in each test case. They take up one line respectively, then n lines of data follow, there are 2 floating numbers in each line expressing coordinates of radio navigation station, then following m lines, there are 2 floating numbers in every line expressing coordinates of smaller islets which are not equipped with radio navigation station. Input is terminated by end of file.

Two positive integers n (3<=n <=100) and m (0 <=m<=20) are provided firstly in each test case. They take up one line respectively, then n lines of data follow, there are 2 floating numbers in each line expressing coordinates of radio navigation station, then following m lines, there are 2 floating numbers in every line expressing coordinates of smaller islets which are not equipped with radio navigation station. Input is terminated by end of file.

4 2
0 0
1 0
1 1
0 1
0.2 0.2
0.5 0.9
4 10
0 0
1 0
1 1
0 1
0.5 0.1
0.5 0.2
0.5 0.3
0.5 0.4
0.5 0.5
0.5 0.6
0.5 0.7
0.5 0.8
0.5 0.9
0.2 0.1

0.00
2.00

1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确

2. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

3. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;