输入N个点的坐标,由程序判断该N个点是否能构成一个凸多边形。(VB)

王朝厨房·作者佚名  2007-01-03
窄屏简体版  字體: |||超大  

用两点式推导直线一般方程(设已知的两点坐标分别为(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

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航