Enter the coordinates of n points, determine whether the N points can constitute a convex polygon by the program.
Solution Idea:
The linear general equation is derived with two o'clock (set two-point coordinates (X1, Y1), (x2, y2), respectively, to X * (Y1-Y2) -Y * (x1-x2) (x1- X2) * Y2-x1 * (Y1-Y2) = 0, let A = Y1-Y2, B = x1-x2, C = (X1-x2) * Y2-x1 * (Y2). That is, AX by C = 0.
For any straight line AX BY C = 0 (A, B is 0), the coordinates (X, Y) of the remaining non-constituent lines are substituted into the straight equation, and if AX BY C> 0, then Point on the right side of the straight line; if AX BY C <0, you will point on the left side of the straight line; if AX BY C = 0, on the straight line.
Example: There is a straight line 5x-6y 3 = 0, a little (5, 0) into the line equation, then the equation is left> 0, and the point (5, 0) is on the right side of the straight line.
Use SET (N, 2) in the program to record each point coordinate, clockwise or counterclockwise sequentially. Use Total (n) to record the value in the line equation. Use S and M separately record points to the equation value or Number of negative points. If the convex polygon, it should be fully or completely negative, ie S> 0 and m> 0. If the concave polygon, S> 0 and M> 0 are also established. If S = 0 and M = 0 are set up, a polygon is not constituted.
The following is a list of procedures: Defint A-ZDoinput "please input n (n> 2)"; N 'Enter NLOOP Until N> 2Dim Set (N, 2): DIM TOTAL (N)' Defines an array for i = 1 to nprint Please Input N ("; I;") Set: "Input" (x, y) "; set (i, 1), set (i, 2) 'use array set (n, 2) record each point coordinate NEXT IFOR i = 1 to np = i 1: if i = n THEN P = 1A = (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) CNEXT JS = 0: m = 0for K = 1 to Nif Total (k)> 0 THEN S = S 1 'Record points for S and M records for straight line IF Total (k) <0 THEN M = M 1NEXT KIF (S> 0 and m> 0) or (s = 0 and m = 0) Then Print "CAN 't. "' Two cases, if there is an emergence, it cannot constitute a convex polygon. Endendness ifnext iPrint "CAN." End
