题目：
平面内有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; } } }
