专注于互联网--专注于架构

2008年9月25日凸多边形:输入N个点的坐标,由程序判断该N个点是否能构成一个凸多边形

输入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,... [阅读全文] [PDF]