pku3304 Segments

解题思路：

 

若存在直线L使得线段在其上的投影有公共区域，那么在这个公共区域中任取一点作L的垂线M，则M必交所有的线段，现在沿着L平移M直到M第一次与某条线段相交于那条线段的某一端点P处，然后将M绕着P转动直到M再次与某条线段相交于那条线段的某一端点处，显然此时与M垂直的直线都是所求的投影直线，也就是任意枚举两个线段的端点，看其他线段是否与这两个端点所构成的直线相交。。。

 

注意题目说两个浮点值小于10^-8就认为是相同的，因而当枚举的两个端点间断小于10^-8就可以看成一个端点，过一个端点的直线显然有无数条直线，与所有线段相交，因而是不能考虑的。以上考虑都是至少含有3条线段的，因而当n=1||n=2时是一定存在这样的直线。

 

import java.io.BufferedInputStream;
import java.util.Scanner;


public class Main {
    static class Point{
        double x,y;
    }

    static final double EXP=1e-8;
    static final int N=105;

    static Point line[][];

    static{
        line=new Point[N][2];
        for(int i=0;i<N;i++) for(int j=0;j<2;j++) line[i][j]=new Point();
    }

    static double det(double x1,double y1,double x2,double y2){
        return x1*y2-x2*y1;
    }

    static double cross(Point a,Point b,Point c){
        return det(b.x-a.x, b.y-a.y, c.x-a.x, c.y-a.y);
    }

    static double dis(Point a,Point b){
        return Math.sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }

    static boolean solve(int n){
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                for(int a=0;a<2;a++){
                    for(int b=0;b<2;b++){
                        if(dis(line[i][a], line[j][b])<EXP) continue;
                        boolean exist=true;
                        for(int k=0;k<n;k++){
                            if(k==i||k==j) continue;
                            if(cross(line[i][a], line[j][b], line[k][0])*cross(line[i][a], line[j][b], line[k][1])>EXP){
                                exist=false;
                                break;
                            }
                        }
                        if(exist) return true;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String []args){
        Scanner sc=new Scanner(new BufferedInputStream(System.in));
        int cases=sc.nextInt();
        while(cases--!=0){
            int n=sc.nextInt();
            for(int i=0;i<n;i++){
                line[i][0].x=sc.nextDouble();line[i][0].y=sc.nextDouble();
                line[i][1].x=sc.nextDouble();line[i][1].y=sc.nextDouble();
            }

            if(n==1||n==2||solve(n)) System.out.println("Yes!");
            else System.out.println("No!");
        }
    }
}