ccw

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;
    public static Point entry;
    public static Point entry2;
    public static Stack<Point> stack;
    public static List<Point> arrayList;
    public static int N;
    public static double X;
    public static double Y;
    public static double PX;
    public static double PY;
    public static double LSX;
    public static double LSY;
    public static double LEX;
    public static double LEY;
    static class Point{
        double x,y;
        public Point(double x,double y) {
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        p = new Point[N];
        PX = Integer.MAX_VALUE;
        PY = Integer.MAX_VALUE;
        arrayList = new ArrayList<Point>();
        stack = new Stack<Point>();
        entry = new Point(Integer.MAX_VALUE, Integer.MAX_VALUE);

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            X = Double.parseDouble(st.nextToken());
            Y = Double.parseDouble(st.nextToken());
            if ((entry.y > Y) || (entry.y == Y && (entry.x > X))) {
                entry.y = Y;
                entry.x = X;
            }
            Point p = new Point(X, Y);
            arrayList.add(p);
        }
        for (int i = 0; i < arrayList.size(); i++) {
            Point tp = arrayList.get(i);
            if (tp.x != entry.x || tp.y != entry.y) {
                stack.push(tp);
            }
        }
//        stack.push(entry);
        for (int i = 0; i < N; i++) {
            Collections.sort(stack, new Comparator<Point>() {
                @Override
                public int compare(Point p1, Point p2) {
                    if (CCW(entry, p1, p2) > 0) {
                        return 1;
                    } else if (CCW(entry, p1, p2) < 0) {
                        return -1;
                    } else {
                        double a = (p2.x - entry.x) * (p2.x - entry.x) + (p2.y - entry.y) * (p2.y - entry.y);
                        double b = (p1.x - entry.x) * (p1.x - entry.x) + (p1.y - entry.y) * (p1.y - entry.y);
                        return (int) (a - b);
                    }
                }
            });
            entry2 = stack.pop();
            entry2 = stack.peek();
            if (entry2.x == entry.x && entry2.y == entry.y) {
                break;
            }else {
                p[i] = entry2;
            }
        }

        while (br.ready()) {
            LineP = new Point[2];
            st = new StringTokenizer(br.readLine());
            LSX= Double.parseDouble(st.nextToken());
            LSY= Double.parseDouble(st.nextToken());
            LEX= Double.parseDouble(st.nextToken());
            LEY= Double.parseDouble(st.nextToken());
            LineP[0] = new Point(LSX, LSY);
            LineP[1] = new Point(LEX, LEY);
            int res = CCW(LineP[0],LineP[1],p[0]);
            for (int i = 1; i < p.length; i++) {
                int resNew = CCW(LineP[0],LineP[1],p[i]);
                if (res != resNew) {
                    System.out.println("BAD");
                    break;
                }
                if (i == p.length-1 && res == resNew) {
                    System.out.println("GOOD");
                }
            }
        }

    }
    //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;
    }
}