输入n个点的坐标,由程序判断该n个点是否能构成一个凸多边形。
解题思路:
用两点式推导直线一般方程(设已知的两点坐标分别为(x1,y1),(x2,y2),得x*(y1-y2)-y*(x1-x2)+(x1-x2)*y2-x1*(y1-y2)=0,令a=y1-y2,b=x1-x2,c=(x1-x2)*y2-x1*(y1-y2)。即ax+by+c=0。
对于任一条直线ax+by+c=0 (a,b不同时为0)，则其余非构成直线的点的坐标(x,y)代入直线方程,若ax+by+c>0,则该点在直线右侧;若ax+by+c<0,则点在直线左侧;若ax+by+c=0,则在直线上。
例：有一直线5x-6y+3=0,一点(5,0)代入直线方程，则方程左式>0所以点(5,0)在直线右侧。
程序中用set(n,2)来记录各点坐标,顺时针或逆时针依次输入.用total(n)来记录坐标在直线方程中的值.用s和m分别记录点代入方程值正或负的点的个数.若是凸多边形,则应全为正或全为负,即s>0和m>0不同时成立.若是凹多边形,则s>0和m>0同时成立.而其中若s=0和m=0同时成立,则不能构成多边形.
以下为程序清单：
defint a-z
do
input "please input n (n>2)"; n '输入n
loop until n > 2
dim set(n, 2): dim total(n) '定义数组
for i = 1 to n
print "please input n("; i; ") set:"
input "(x,y)"; set(i, 1), set(i, 2) '用数组set(n,2)记录各点坐标
next i
for i = 1 to n
p = i + 1: if i = n then p = 1
a = (set(i, 2) - set(p, 2))
b = (set(i, 1) - set(p, 1))
c = (set(i, 1) - set(p, 1)) * set(p, 2) - set(i, 1) * (set(i, 2) - set(p, 2))
for j = 1 to n
total(j) = a * set(j, 1) - b * set(j, 2) + c
next j
s = 0: m = 0
for k = 1 to n
if total(k) > 0 then s = s + 1 '用s和m记录点对于直线的位置
if total(k) < 0 then m = m + 1
next k
if (s > 0 and m > 0) or (s = 0 and m = 0) then
print "can't." '两种情况任一种，若有一次出现，就不能构成凸多边形。
end
end if
next i
print "can."
end
