admin管理员组文章数量:1130349
【poj
题目链接：
题意：给出一些直线，直线与直线切割的线段是围墙，只能从围墙中间穿过，问最少穿过几层墙才能到达终点
看了hzwer的，觉得好有道理，虽然说是中点，但其实直接求每个端点就ok了
1 /*************************************************************************
2 > File Name: poj1066.cpp
3 # File Name: poj1066.cpp
4 # Author : xiaobuxie
5 # QQ : 760427180
6 # Email:760427180@qq.com
7 # Created Time: 2019年09月21日 星期六 15时11分27秒
8 ************************************************************************/
9
10 #include<iostream>
11 #include<cstdio>
12 #include<map>
13 #include<cmath>
14 #include<cstring>
15 #include<set>
16 #include<queue>
17 #include<vector>
18 #include<algorithm>
19 using namespace std;
20 typedef long long ll;
21 #define inf 0x3f3f3f3f
22 #define pq priority_queue<int,vector<int>,greater<int> >
23 const double eps = 1e-8;
24 const int N=50;
25 int sgn(double x){
26 if(fabs(x)<eps) return 0;
27 if(x<0) return -1;
28 return 1;
29 }
30 struct Point{
31 double x,y;
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.y-b.x*y;
37 }
38 }P[N<<2];
39 struct Line{
40 Point s,e;
41 }L[N];
42 bool inter(Line l1,Line l2){
43 return
44 max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&
45 max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&
46 max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&
47 max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&
48 sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s)) <= 0 &&
49 sgn((l1.s-l2.s)^(l2.e-l1.s))*sgn((l1.e-l2.s)^(l2.e-l2.s)) <= 0;
50 }
51 int main(){
52 int n; scanf("%d",&n);
53 if(!n){
54 printf("Number of doors = 1");
55 return 0;
56 }
57 double x1,x2,y1,y2,ex,ey;
58 for(int i=1;i<=n;++i){
59 scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
60 L[i]=(Line){(Point){x1,y1},(Point){x2,y2}};
61 P[i*2]=(Point){x1,y1}; P[i*2-1]=(Point){x2,y2};
62 }
63 scanf("%lf %lf",&ex,&ey);
64 Point ed=(Point){ex,ey};
65 int ans=10000000;
66 for(int i=1;i<=2*n;++i){
67 Line l1=(Line){ed,P[i]};
68 int tem=0;
69 for(int j=1;j<=n;++j){
70 if(i==2*j || i==2*j-1) continue;
71 if(inter(l1,L[j])) ++tem;
72 }
73 ans=min(ans,tem);
74 //cerr<<ans<<endl;
75 }
76 //cerr<<ans<<endl;
77 printf("Number of doors = %d",ans+1);
78 return 0;
79 } View Code
转载于:.html
【poj
题目链接：
题意：给出一些直线，直线与直线切割的线段是围墙，只能从围墙中间穿过，问最少穿过几层墙才能到达终点
看了hzwer的，觉得好有道理，虽然说是中点，但其实直接求每个端点就ok了
1 /*************************************************************************
2 > File Name: poj1066.cpp
3 # File Name: poj1066.cpp
4 # Author : xiaobuxie
5 # QQ : 760427180
6 # Email:760427180@qq.com
7 # Created Time: 2019年09月21日 星期六 15时11分27秒
8 ************************************************************************/
9
10 #include<iostream>
11 #include<cstdio>
12 #include<map>
13 #include<cmath>
14 #include<cstring>
15 #include<set>
16 #include<queue>
17 #include<vector>
18 #include<algorithm>
19 using namespace std;
20 typedef long long ll;
21 #define inf 0x3f3f3f3f
22 #define pq priority_queue<int,vector<int>,greater<int> >
23 const double eps = 1e-8;
24 const int N=50;
25 int sgn(double x){
26 if(fabs(x)<eps) return 0;
27 if(x<0) return -1;
28 return 1;
29 }
30 struct Point{
31 double x,y;
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.y-b.x*y;
37 }
38 }P[N<<2];
39 struct Line{
40 Point s,e;
41 }L[N];
42 bool inter(Line l1,Line l2){
43 return
44 max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&
45 max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&
46 max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&
47 max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&
48 sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s)) <= 0 &&
49 sgn((l1.s-l2.s)^(l2.e-l1.s))*sgn((l1.e-l2.s)^(l2.e-l2.s)) <= 0;
50 }
51 int main(){
52 int n; scanf("%d",&n);
53 if(!n){
54 printf("Number of doors = 1");
55 return 0;
56 }
57 double x1,x2,y1,y2,ex,ey;
58 for(int i=1;i<=n;++i){
59 scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
60 L[i]=(Line){(Point){x1,y1},(Point){x2,y2}};
61 P[i*2]=(Point){x1,y1}; P[i*2-1]=(Point){x2,y2};
62 }
63 scanf("%lf %lf",&ex,&ey);
64 Point ed=(Point){ex,ey};
65 int ans=10000000;
66 for(int i=1;i<=2*n;++i){
67 Line l1=(Line){ed,P[i]};
68 int tem=0;
69 for(int j=1;j<=n;++j){
70 if(i==2*j || i==2*j-1) continue;
71 if(inter(l1,L[j])) ++tem;
72 }
73 ans=min(ans,tem);
74 //cerr<<ans<<endl;
75 }
76 //cerr<<ans<<endl;
77 printf("Number of doors = %d",ans+1);
78 return 0;
79 } View Code
转载于:.html
本文标签： POJ
版权声明：本文标题：【poj 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://it.en369.cn/IT/1687722846a133562.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论