输入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 
|