http://poj.org/problem?id=3304
题意：求是否存在一条直线，使所有线段到这条直线的投影至少有一个交点。
题解“：
1：把问题转化为是否存在一条直线与每条线段都有交点。证明：若存在一条直线l和所有线段相交，作一条直线m和l垂直
，则m就是题中要求的直线，所有线段投影的一个公共点即为垂足。
所以我们只要枚举所有的端点构成的直线 ，就可以了，叉积 判断 是否直线和线段相交。
2：枚举两两线段的各一个端点，连一条直线，再判断剩下的线段是否都和这条直线有交点。
证明：若有l和所有线段相交，则可保持l和所有线段相交，上下 平移l到和某一线段交于端点停止（“移不动了”）。然后绕这个交点旋转。也是转到“转不动了”（和另一线段交于其一个端点）为止。这样就找到了一个新的l满足题意，而且经过其中两线段的端点。
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 120
15 #define eps 1e-8
16 #define inf 100000000
17 #define mx 1<<60
18 #define ll __int64
19 using namespace std;
20
21 struct point
22 {
23 double x;
24 double y;
25 }up[maxn],dp[maxn],p[maxn*2];
26 double ans ;
27 int n,num ;
28 int dbcmp(double x)
29 {
30 if(fabs(x) < eps) return 0;
31 if(x< 0) return -1;
32 else return 1 ;
33
34 }
35 double det(double x1,double y1,double x2,double y2)
36 {
37 return x1*y2 - x2*y1 ;
38 }
39 double cross(point a,point b,point c)
40 {
41 return det(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);
42 }
43
51 bool solve( )
52 {
53
54 int i,j,k;
55 for(i = 0 ; i< num;i++)
56 {
57 for(j = 0 ; j < num;j++)
58 {
59 if(i == j)continue ;
60 if(sqrt((p[i].x - p[j].x)*(p[i].x - p[j].x) + (p[i].y - p[j].y)*(p[i].y - p[j].y)) < eps)continue ;//注意这个判断 错在这好几次
61 int f = 0 ;
62 for(k = 0 ; k < n;k++)
63 {
64 if(dbcmp(cross(p[i],p[j],up[k]))*dbcmp(cross(p[i],p[j],dp[k])) > 0)
65 {
66 f = 1;
67 break;
68 }
69
70
71 }
72 if(f == 0) return true ;
73
74 }
75 }
76 return false ;
77
78 }
79
80 int main()
81 {
82 int i,j;
83 //freopen("data.txt","r",stdin);
84 int t;
85 scanf("%d",&t);
86
87 while(t--)
88 {
89 scanf("%d",&n);
90 num = 0 ;
91
92 for(i = 0;i< n;i++)
93 {
94 scanf("%lf %lf %lf %lf",&up[i].x,&up[i].y,&dp[i].x,&dp[i].y);
95 p[num].x = up[i].x;
96 p[num].y = up[i].y ;
97 num++;
98 p[num].x = dp[i].x;
99 p[num].y = dp[i].y ;
100 num ++;
101
102
103
104 }
105 if(n == 1|| n == 2)
106 {
107 puts("Yes!");
108
109 continue ;
110
111 }
112 bool f = false ;
113 f = solve() ;
114 if(f)puts("Yes!");
115 else puts("No!");
116 }
117 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 120
15 #define eps 1e-8
16 #define inf 100000000
17 #define mx 1<<60
18 #define ll __int64
19 using namespace std;
20
21 struct point
22 {
23 double x;
24 double y;
25 }up[maxn],dp[maxn],p[maxn*2];
26 double ans ;
27 int n,num ;
28 int dbcmp(double x)
29 {
30 if(fabs(x) < eps) return 0;
31 if(x< 0) return -1;
32 else return 1 ;
33
34 }
35 double det(double x1,double y1,double x2,double y2)
36 {
37 return x1*y2 - x2*y1 ;
38 }
39 double cross(point a,point b,point c)
40 {
41 return det(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);
42 }
43
51 bool solve( )
52 {
53
54 int i,j,k;
55 for(i = 0 ; i< num;i++)
56 {
57 for(j = 0 ; j < num;j++)
58 {
59 if(i == j)continue ;
60 if(sqrt((p[i].x - p[j].x)*(p[i].x - p[j].x) + (p[i].y - p[j].y)*(p[i].y - p[j].y)) < eps)continue ;//注意这个判断 错在这好几次
61 int f = 0 ;
62 for(k = 0 ; k < n;k++)
63 {
64 if(dbcmp(cross(p[i],p[j],up[k]))*dbcmp(cross(p[i],p[j],dp[k])) > 0)
65 {
66 f = 1;
67 break;
68 }
69
70
71 }
72 if(f == 0) return true ;
73
74 }
75 }
76 return false ;
77
78 }
79
80 int main()
81 {
82 int i,j;
83 //freopen("data.txt","r",stdin);
84 int t;
85 scanf("%d",&t);
86
87 while(t--)
88 {
89 scanf("%d",&n);
90 num = 0 ;
91
92 for(i = 0;i< n;i++)
93 {
94 scanf("%lf %lf %lf %lf",&up[i].x,&up[i].y,&dp[i].x,&dp[i].y);
95 p[num].x = up[i].x;
96 p[num].y = up[i].y ;
97 num++;
98 p[num].x = dp[i].x;
99 p[num].y = dp[i].y ;
100 num ++;
101
102
103
104 }
105 if(n == 1|| n == 2)
106 {
107 puts("Yes!");
108
109 continue ;
110
111 }
112 bool f = false ;
113 f = solve() ;
114 if(f)puts("Yes!");
115 else puts("No!");
116 }
117 }