输入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 
|
本类阅读TOP10