题意:给出n条线段两个端点的坐标,问所有线段投影到一条直线上,如果这些所有投影至少相交于一点就输出Yes!,否则输出No!。


题解:假设存在一条这样的直线,那么过这条直线的公共投影区域作一条垂线,则该垂线必定与所有线段相交。所以问题变成了如何找这一条直线,然后这条直线必过线段的两个端点。考虑到线段数目不是很多,所以我们只需要枚举所有线段的两个端点组成的直线即可。注意用精度判断点是否重合!


代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=5005;
const double eps=1e-12;
struct Point{
    double x, y;
    Point(double x=0, double y=0):x(x),y(y){}
    Point operator-(const Point &cmp)const{return Point(x-cmp.x, y-cmp.y);}
    double operator*(const Point &cmp)const{return x*cmp.x+y*cmp.y;}
};
struct Line{
    Point s, e;
    Line(){}
    Line(Point s, Point e):s(s), e(e){}
    bool operator <(const Line &cmp)const {
        return s.x<cmp.s.x;
    }
};
typedef Point Vector;
Vector operator +(Vector A, Vector B){return Vector(A.x+B.x, A.y+B.y);}
Vector operator -(Point A, Point B){return Vector(A.x-B.x, A.y-B.y);}
Vector operator *(Vector A, double p){return Vector(A.x*p, A.y*p);}
Vector operator /(Vector A, double p){return Vector(A.x/p, A.y/p);}
int dcmp(double x){
    if(fabs(x)<eps)return 0;else return x<0?-1:1;
}
double Cross(Vector A, Vector B){return A.x*B.y-A.y*B.x;}
double Area2(Point A, Point B, Point C){return Cross(B-A, C-A);}
double dist(Point A, Point B){return sqrt((B-A)*(B-A));}
bool line_make_point(Line l1, Line l2){
    return dcmp(Area2(l2.s, l1.s, l1.e))*dcmp(Area2(l2.e, l1.s, l1.e))<=0;
}
int n;
Line line[maxn];
Point point[maxn];
bool check(Line l1){
    for(int i=0;i<n;i++){
        if(line_make_point(l1, line[i])==0)return 0;
    }
    return 1;
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i=0;i<n;i++){
            scanf("%lf%lf%lf%lf", &point[i*2].x, &point[i*2].y, &point[i*2+1].x, &point[i*2+1].y);
            line[i]=Line(point[i*2], point[i*2+1]);
        }
        bool ans=0;
        for(int i=0;i<n*2;i++){
            for(int j=i+1;j<n*2;j++){
                if(dcmp(dist(point[i], point[j]))!=0){
                    if(check(Line(point[i], point[j]))){
                        ans=1;break;
                    }
                }
            }
        }
        printf("%s\n", ans?"Yes!":"No!");
    }
    return 0;
}