很郁悶的一題，第一次碰到使用不同的編譯器，一個超時（C++），一個AC的情況（G++）。。。

首先題中的要求等價于：存在一條直線l和所有的線段都相交。

證明：若存在一條直線l和所有線段相交，作一條直線m和l垂直，則m就是題中要求的直線所有線段投影的一個公共點即為垂足。（l和每條線段的交點沿l投影到m上的垂足處）反過來，若存在m，所有線段在m上的投影有公共點，則過這點垂直于m作直線l， l一定和所有線段相交。

然后證存在l和所有線段相交等價于存在l過某兩條線段的各一個端點且和所有線段相交。充分性顯然。必要性：若有l和所有線段相交，則可保持l和所有線段相交，左右平移l到和某一線段交于端點停止（“移不動了”）。然后繞這個交點旋轉。也是轉到“轉不動了”（和另一線段交于其一個端點）為止。這樣就找到了一個新的l。

于是本題可歸結為枚舉兩兩線段的各一個端點，連一條直線，再判斷剩下的線段是否都和這條直線有交點。

注意：數據中有所有線段都縮成一個點的情況。

 1#include<cstdio>
 2#include<cstring>
 3#include<algorithm>
 4#include<vector>
 5#include<complex>
 6#include<cmath>
 7#include<iostream>
 8using namespace std;
 9
10typedef complex<double> point;
11
12const int maxn = 330;
13const double eps = 1e-8;
14const double pi = acos( -1.0 );
15const double inf = 1e20;
16struct line
17{
18    point a, b;
19    line( ){ }
20    line( point u, point v ) : a( u ), b( v ){ }
21};
22
23point p[maxn<<1];
24line l[maxn];
25
26double operator ^( point p1, point p2 ) { return imag( conj(p1) * p2 ); }
27double operator &( point p1, point p2 ) { return real( conj(p1) * p2 ); }
28int dblcmp( double x ) { return ( x < -eps ? -1 : x > eps ); }
29
30bool same( point p1, point p2 )
31{
32    if( dblcmp( real(p1)- real(p2) ) == 0 && dblcmp( imag(p1) - imag(p2) ) == 0 )
33        return true;
34    return false;
35}
36// 判斷線段l1是否與直線l2相交
37bool segcross( line l1, line l2 )
38{
39    if( dblcmp( l1.a - l2.a ^ l2.b - l2.a ) * 
40        dblcmp( l2.b - l2.a ^ l1.b - l2.a ) >= 0 )
41        return true;
42    return false;
43}
44
45bool check( point p1, point p2, int n )
46{
47    line l0 = line( p1, p2 );
48    for( int k = 0; k < n; k++ )
49        if( !segcross( l[k], l0 ) ) return false;
50    return true;
51}
52
53bool solve( int n )
54{
55    int len = n << 1;
56    int cnt = 0;
57    for( int i = 0; i < len; i++ )
58    {
59        for( int j = i + 1; j < len; j++ )
60        {
61            if( same( p[i], p[j] ) ) 
62            {
63                cnt++;
64                continue;
65            }
66            if( check( p[i], p[j], n ) )
67                return true;
68        }
69    }
70    if( cnt == len * ( len - 1 ) / 2 ) return true;
71    return false;
72}
73
74int main( )
75{
76    int t, n;
77    double x1, x2, y1, y2;
78    //freopen("1005.in","r",stdin);
79    //freopen("out.txt","w",stdout);
80    scanf("%d",&t);
81    while( t-- )
82    {
83        scanf("%d",&n);
84        int len = 0;
85        for( int i = 0; i < n; i++ )
86        {
87            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
88            p[len++] = point( x1, y1 );
89            p[len++] = point( x2, y2 );
90            l[i] = line( p[len-2], p[len-1] );
91        }
92        if( solve( n ) ) printf("Yes\n");
93        else printf("No\n");
94    }
95    return 0;
96}
97