CCW 算法（ POJ_1912）

本文主要是介绍CCW 算法（ POJ_1912），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 判断点和线的位置关系

向量叉积是用来判断两个向量之间方向的
他的计算方法如下：


假设两个向量分别为a-> =(x1,y1),b-> =(x2,y2)，则a向量 与b向量 的叉积如下定义：
a ×b =x1⋅y2−x2⋅y1
其中，符号×用来表示向量叉积运算。而a向量 和b向量 都是以坐标原点为起点，以上面给出的坐标：(x1,y1), (x2,y2 为终点的两个向量。


根据这个叉积的算法，我们不难得到以下规律：
若a ×b >0，则a 在b 的顺时针方向
若a ×b <0，则a 在b 的逆时针方向
若a ×b =0，则a 与b 共线


a x b = |a|.|b|.sinθ
** = x1.y2 - x2.y1**
例如：
三个点： A:(x1,y1) B:(x2,y2) C**:(x3,y3)
判断点 C 在 向量 AB 的左边还是右边？
交叉想成法 ：
x1 x2 x3 x1**
y1 y2 y3 y1
AB x AC = (x1y2 + x2y3 + x3y1) -（y1x2 + y2x3 + y3x1）
当 >0 时 ，则 C 点在 AB 的左侧

static class Point{double x,y;public Point(double x,double y) {this.x = x;this.y = y;}
}
//ccw
private static int CCW(Point p1, Point p2, Point p3) {return (p1.x*p2.y+p2.x*p3.y+p3.x*p1.y)-(p1.y*p2.x+p2.y*p3.x+p3.y*p1.x) >0? 1:-1;
}

例题： POJ_1912 CCW算法 http://poj.org/problem?id=1912

package jihe;import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;
/*** poj_1912* @author Administrator*/
public class CCW_1912 {public static Point[] p;public static Point[] LineP

这篇关于CCW 算法（ POJ_1912）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---