2016华为校招之输入一系列坐标点,从中找出部分点，使其构成的多边形面积最大

在笛卡尔平面内输入一系列坐标点，从其中选出任意多点，使其组成的多边形面积最大。

输入: a) 输入由一行文本组成，第一个是一个整数，表示输入坐标的个数；紧跟其后的是一个英文的分号(;)。然后就是N（第一个整数值）个坐标点，坐标点之间使用英文分号(;)。坐标点的x和y值使用英文逗号(,)分隔。坐标点的取值范围在[-1000,1000]，坐标值均是整数；

b) 输入的点的数量最大 65535 个；至少有三个；

输出: a）在同一行上输出所有凸多边形的顶点的坐标，坐标值必须是整数；

b）点之间用英文分号字符分隔；行最后的分号必须省略；

c）一个点的x和y坐标之间，用英文逗号字符分隔；

d）如果某个点正好落在凸多边形的边上，则不应该输出该点；

e）以坐标X值排序，从X值最小的点开始，按顺时针方向，依次输出组成最大凸多边形的顶点坐标。

样例输入: 13;-3,-3;1,3;2,-4;6,1;-2,-2;4,5;1,-2;1,4;-2,3;-4,1;-1,1;2,2;1,-1

样例输出: -4,1;-2,3;4,5;6,1;2,-4;-3,-3

line = raw_input()
list1 = line.split(";")
number = list1[0]
x = []
y = []
result = ''
for i in range(1, len(list1)):
    x.append(int(list1[i].split(",")[0]))
    y.append(int(list1[i].split(",")[1]))
index = 0
min_value = 100
for i in x: 
    if i < min_value:
        min_value_index = index
        min_value = i
    index += 1
result += str(min_value) + "," + str(y[min_value_index])+ ";"
status = 1
max_value1 = 0
current_x = x[min_value_index]
current_y = y[min_value_index]
while 1:
    temp_index = None
    for i in range(len(list1)-1):
        if x[i]-current_x>0 and float((y[i]-current_y))/(x[i]-current_x+0.000001)>max_value1:
            temp_index = i
            max_value1 = float((current_y-y[i]))/(current_x-x[i]+0.000001)
    if temp_index is not None:
        current_x = x[temp_index]
        current_y = y[temp_index]
        result += str(current_x) + "," + str(current_y)+ ";"
        max_value1 = 0
    else:
        status = 2
        break
min_value1 = 0
while 1:
    temp_index = None
    for i in range(len(list1)-1):
        if x[i]-current_x>0 and float((current_y-y[i]))/(current_x-x[i])<min_value1:
            temp_index = i
            min_value1 = float((current_y-y[i]))/(current_x-x[i])
    if temp_index is not None:
        current_x = x[temp_index]
        current_y = y[temp_index]
        result += str(current_x) + "," + str(current_y)+ ";"
        min_value1 = 0
    else:
        status = 3
        break
max_value2 = 0
while 1:
    temp_index = None
    for i in range(len(list1)-1):
        if x[i]-current_x<0 and float((current_y-y[i]))/(current_x-x[i])>max_value2:
            temp_index = i
            max_value2 = float((current_y-y[i]))/(current_x-x[i])
    if temp_index is not None:
        current_x = x[temp_index]
        current_y = y[temp_index]
        result += str(current_x) + "," + str(current_y)+ ";"
        max_value2 = 0
    else:
        status = 4
        break
min_value2 = -10000000
while 1:
    temp_index = None
    for i in range(len(list1)-1):
        if x[i]-current_x<0 and float((current_y-y[i]))/(current_x-x[i]+0.000001)>min_value2:
            temp_index = i
            min_value2 = float((current_y-y[i]))/(current_x-x[i]+0.000001)
    if temp_index is not None and temp_index != min_value_index:
        current_x = x[temp_index]
        current_y = y[temp_index]
        result += str(current_x) + "," + str(current_y)+ ";"
        min_value2 = 0
    else:
        break
print result[:-1]