个人主页网页设计素材,网站优化排名提升,wordpress自定义侧边栏,昆明小程序推广1 // 判断线段和直线相交 POJ 33042 // 思路#xff1a;3 // 如果存在一条直线和所有线段相交#xff0c;那么平移该直线一定可以经过线段上任意两个点#xff0c;并且和所有线段相交。4 5 #include cstdio6 #include cstring7 #include iostream8 … 1 // 判断线段和直线相交 POJ 33042 // 思路3 // 如果存在一条直线和所有线段相交那么平移该直线一定可以经过线段上任意两个点并且和所有线段相交。4 5 #include cstdio6 #include cstring7 #include iostream8 #include algorithm9 #include map
10 #include set
11 #include queue
12 #include stdlib.h
13 #include cmath
14 using namespace std;
15 typedef long long LL;
16 const LL inf 1e18;
17 const int N 5000;
18 const double eps 1e-8;
19
20 int sgn(double x){
21 if(fabs(x)eps) return 0;
22 if(x0) return -1;
23 return 1;
24 }
25
26 struct Point{
27 double x,y;
28 Point(){}
29 Point(double _x,double _y){
30 x_x;y_y;
31 }
32 Point operator -(const Point b)const{
33 return Point(x-b.x,y-b.y);
34 }
35 double operator *(const Point b)const{
36 return x*b.xy*b.y;
37 }
38 double operator ^(const Point b)const{
39 return x*b.y-y*b.x;
40 }
41 };
42
43 struct Line{
44 Point s,e;
45 Line(){}
46 Line(Point _s,Point _e){
47 s_s,e_e;
48 }
49 };
50
51 double xmult(Point p0,Point p1,Point p2){
52 return (p1-p0)^(p2-p0);
53 }
54
55 bool Seg_inter_line(Line l1,Line l2){
56 return sgn(xmult(l2.s,l1.s,l1.e))*sgn(xmult(l2.e,l1.s,l1.e))0;
57 }
58
59 double dist(Point a,Point b){
60 return sqrt((a-b)*(a-b));
61 }
62 Line line[N];
63 bool work(Line l1,int n){
64 if(sgn(dist(l1.s,l1.e))0) return false;
65 for(int i0;in;i){
66 if(Seg_inter_line(l1,line[i])false) return false;
67 }
68 return true;
69 }
70 int main(){
71 int n,T;
72 scanf(%d,T);
73 while(T--){
74 scanf(%d,n);
75 double x1,y1,x2,y2;
76 for(int i0;in;i){
77 scanf(%lf%lf%lf%lf,x1,y1,x2,y2);
78 line[i]Line(Point(x1,y1),Point(x2,y2));
79 }
80 bool flagfalse;
81 for(int i0;in;i){
82 for(int j0;jn;j){
83 if(work(Line(line[i].s,line[j].e),n)||work(Line(line[i].s,line[j].s),n)||work(Line(line[i].e,line[j].e),n)||work(Line(line[i].e,line[j].s),n)){
84 flagtrue;
85 break;
86 }
87 }
88 if(flag) break;
89 }
90 if(flag) puts(Yes!);
91 else puts(No!);
92 }
93 return 0;
94 } 转载于:https://www.cnblogs.com/ITUPC/p/5851135.html
