Description

Given n segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in common.

Input

Input begins with a number T showing the number of test cases and then, T test cases follow. Each test case begins with a line containing a positive integer n ≤ 100 showing the number of segments. After that, n lines containing four real numbers x₁y₁x₂y₂ follow, in which (x₁, y₁) and (x₂, y₂) are the coordinates of the two endpoints for one of the segments.

Output

For each test case, your program must output "Yes!", if a line with desired property exists and must output "No!" otherwise. You must assume that two floating point numbers a and b are equal if |a - b| < 10^-8.

Sample Input

321.0 2.0 3.0 4.04.0 5.0 6.0 7.030.0 0.0 0.0 1.00.0 1.0 0.0 2.01.0 1.0 2.0 1.030.0 0.0 0.0 1.00.0 2.0 0.0 3.01.0 1.0 2.0 1.0

Sample Output

Yes!Yes!No!

题意：

求n条线段在一条直线上的投影是否有交点

思路：

假设存在这样的一个交点，那么过交点做投影直线的垂线，必定和所有的线段相交，然后就将问题化为构造一条和所有线段相交的直线。通过每次枚举两个线段的

端点作出直线。

#include "stdio.h"#include "iostream"#include "algorithm"#include "cmath"#include "string.h"using namespace std;const int maxn = 100 + 10;const double eps = 1e-8;struct Point {    double x, y;    Point(double x=0.0, double y=0.0) :x(x), y(y) {}};typedef Point Vector;Vector operator - (Point A,Point B) {
   return Vector(A.x-B.x,A.y-B.y);}int dcmp(double x) {
   if (fabs(x) < eps) return 0;return x < 0? -1: 1;} double Dot(Vector A,Vector B) {
   return A.x*B.x+A.y*B.y;}double Length(Point A) {
   return sqrt(Dot(A,A));}double Cross(Vector A,Vector B) {
   return A.x*B.y-A.y*B.x;}int N;Point p[maxn][4];bool getcross(Point L, Point S) {    if (dcmp(Length(S - L)) == 0) return false;    for (int i = 0; i < N; i++) {        if (dcmp(Cross(S-L, p[i][0]-L)*Cross(S-L, p[i][1]-L))>0) return false;    }    return true;}void solve() {    for (int i = 0; i < N; i++) {        for (int j = 0; j < N; j++) {            if (getcross(p[j][0],p[i][0])||getcross(p[j][1],p[i][0])||                getcross(p[j][1],p[i][1])||getcross(p[j][0],p[i][1])) {                printf("Yes!\n"); return ;            }        }    }    printf("No!\n");}int main(int argc, char const *argv[]){    int T;    scanf("%d", &T);    while (T--) {        scanf("%d", &N);        for (int i = 0; i < N; i++) {            scanf("%lf%lf%lf%lf", &p[i][0].x, &p[i][0].y, &p[i][1].x, &p[i][1].y);        }        solve();    }    return 0;}/*1675 93 42 4547 44 87 3010 55 36 1432 81 73 5729 84 75 2318 38 99 95*/