算法-点线关系-投影在线段上各点距离最大

题目：

平面内有N个点，一个线段（2个顶点），一束垂直于线段的光照射后，点会在线段上有影子，求影子点里面最长距离。

输入：

第一行测试用例个数T；

第二行第一个测试用例的点个数N；

下面N行每行给出2个整数，用空格隔开表示点的x,y坐标；

再下一行给出表示光方向和大小的点坐标x,y,空格隔开；

再下一行给出线段的2个顶点左边，依次x1,y1,x2,y2，用空格隔开。

输出：

#+测试用例个数+最长的距离

**************************************************

分析：

先判断光向量的相对于线段的方向。

当光点坐标y=0，若x>0则1；否则-1；

若y>0,则-1，y<0,则1；

表示线段的方向也要保证：

若光与X轴平行，则y小的为起始点，y大的为方向

若光不与平行，则x小的为起始点，x大的为方向

使用ccw公式计算Poing A，B，C坐标，若大于0，则1；若小于0，则-1；否则0；

--------------------------------------------------------------------------

使用ccw计算点与线段的关系，保证光和点在线同侧，且投影后的点在线段上。

若投影点数少于2个，则答案为0.0；

以线段一个顶点为起点，计算满足条件的每一个点到起点的距离，然后用最大的减去最小的，得到答案。

以下是代码分析：

import java.io.*;
import java.util.*;

public class Solution{

    static int T,N;
    static Point[] points;
    static Point G;
    static Point[] L;
    static List<Point> list = new ArrayList<>();
    static double ans;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        T = Integer.parseInt(bf.readLine());
        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(bf.readLine());
            points = new Point[N];
            L = new Point[2];
            // get points
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(bf.readLine());
                points[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            }

            //get light point
            st = new StringTokenizer(bf.readLine());
            G = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

            // get Line
            st = new StringTokenizer(bf.readLine());
            Point p1 = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            Point p2 = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

            if (p1.x == p2.x){
                if (p1.y < p2.y){
                    L[0] = p1;
                    L[1] = p2;
                } else {
                    L[0] = p2;
                    L[1] = p1;
                }
            } else if (p1.x < p2.x){
                L[0] = p1;
                L[1] = p2;
            } else {
                L[0] = p2;
                L[1] = p1;
            }

            method();

            System.out.println("#" + t + " " + ans);
        }
    }

    static void method(){
        list.clear();
        getMapingPoint();
        if (list.size() < 2) {
            ans = 0.0;
            return;
        }

        double[] arr = new double[list.size()];
        double dx, dy;
        for (int i = 0; i < list.size(); i++) {
            Point p = list.get(i);
            dx = p.x - L[0].x;
            dy = p.y - L[0].y;
            arr[i] = Math.sqrt(dx*dx + dy*dy);
        }
        Arrays.sort(arr);
        ans = arr[arr.length-1] - arr[0];
    }

    static void getMapingPoint(){
        int fx = getGuangFX();
        for (int i = 0; i < N; i++) {
            if (ccw(L[0], L[1], points[i]) == fx){
                check(points[i]);
            }
        }
    }

    static void check(Point p0){
        Point p1 = L[0];
        Point p2 = L[1];
        double minX = Math.min(p1.x, p2.x);
        double maxX = Math.max(p1.x, p2.x);
        double minY = Math.min(p1.y, p2.y);
        double maxY = Math.max(p1.y, p2.y);
        if (G.x == 0) {
            if (p0.x >= minX && p0.x <= maxX) {
                list.add(p0);
                return;
            }
        }

        if (G.y == 0) {
            if (p0.y >= minY && p0.y <= maxY) {
                list.add(p0);
                return;
            }
        }

        double dx = p1.x - p2.x;
        double dy = p1.y - p2.y;
        double x = (dx*dx*p0.x + dy*dy*p1.x + dx*dy*(p0.y - p1.y))/(dx*dx + dy*dy);
        double y = (dy*x + dx*p1.y - dy*p1.x) / dx;
        if (x >= minX && x <= maxX && y >= minY && y <= maxY)
            list.add(new Point(x, y));
    }

    static int getGuangFX(){
        if (G.y==0)
            return G.x > 0 ? 1 : -1;
        else
            return G.y > 0 ? -1 : 1;
    }

    static int ccw(Point A, Point B, Point C){
        double res = A.x*B.y + B.x*C.y + C.x*A.y - A.y*B.x - B.y*C.x -C.y*A.x;
        if (res > 0)
            return 1;
        else if (res <0)
            return -1;
        else
            return 0;
    }

    static class Point{
        double x;
        double y;
        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }
}