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]