UVALive3905 流星 |
【题目描述】:在夜空下,放置一个摄像头,已知,摄像头左下角在(0,0),右上角由输入给定(w,h)。再给出n颗流星的初始位置(夜空范围内,不一定在摄像头范围内),矢量速度(VX,VY),求从开始,整个过程中,镜头内最多看到几颗流星。注意,在流星在边框上时看不到。 |
【思路分析】: 【一】遇到物理问题一般退化成数字模型。列两个不等式 0<x+vx*t<w (注意是开区间) 0<y+vy*t<h 【二】这样能解出一个关于变量t的公共区间,但是要注意,随着vx的正负,除完可能要变号。书上提供一个很好的方法,详细见代码,两边逼近最后的区间。 这样我们就得到了n个区间(当然,如果区间左端点大于等于右端点,应该舍去) 最终问题变成,在这数轴上的n条线段,找出一条t=x的竖线,使它穿过的横线最多。X即为所求的解。 【三】我们假设从负无穷点处开始移动这条竖线,当它从一条直线的左端点偏左(+eps),这条竖线上多穿了一条,从一条直线的右端点(这里不用考虑eps了,为什么,因为本身是开区间了),穿过的线少了一条。 但是我们不可能模拟一条直线移动(精度不够)。但是我们是能够跳跃的,即只考虑两个端点,所以先将线段排序(1、左端小的优先;2、右端小的优先)。排序的目的是O(n)的复杂度的扫描,不重不漏。 【四】额外思考:如果不排序呢?我们可以枚举每条边,在它的右端点靠左一点的位置t检测所有边是否包含这个t,最终记录最大的边数即可。但是这样复杂度就成了N*N。而排序的方法约为Nlog2(N)+N. |
【完整代码】: 1 #include<iostream> 2 3 #include<stdio.h> 4 5 #include<string.h> 6 7 #include<algorithm> 8 9 #include<stdlib.h> 10 11 #include<math.h> 12 13 #include<queue> 14 15 #include<vector> 16 17 #include<set> 18 19 #include<map> 20 21 #define MAXN 200000+5 22 23 #define MAXM 400000+5 24 25 #define oo 1e9 26 27 #define eps 0.001 28 29 #define PI acos(-1.0)//这个精确度高一些 30 31 #define REP1(i,n) for(int i=0;i<=(n);i++) 32 33 #define REP2(i,n) for(int i=1;i<=(n);i++) 34 35 #define LL long long 36 37 using namespace std; 38 39 40 41 struct Event 42 43 { 44 45 int lor;//左端点为1,右端点为2 46 47 double p; 48 49 Event(){} 50 51 Event(int ll,double pp){lor=ll;p=pp;} 52 53 bool operator <(const Event& x) const 54 55 { 56 57 if (p==x.p) return lor>x.lor; 58 59 else return p<x.p; 60 61 } 62 63 }event[MAXM]; 64 65 66 67 int cas,w,h,n; 68 69 double l,r; 70 71 72 73 double maxd(double a,double b) 74 75 { 76 77 if (a>b) return a;else return b; 78 79 } 80 81 double mind(double a,double b) 82 83 { 84 85 if (a<b) return a;else return b; 86 87 } 88 89 void getVAL(double s,double v,double up)//满足0<s+vt<up 90 91 { 92 93 if (v==0) 94 95 if ( s<=0 || s>=up)//注意边界 96 97 r=l-1;//这个区间不存在 98 99 else return;//star将一直存在 100 101 if (v>0) {l=maxd(l,-s/v),r=mind(r,(up-s)/v);} 102 103 if (v<0) {l=maxd(l,(up-s)/v),r=mind(r,-s/v);} 104 105 return; 106 107 } 108 109 110 111 112 113 int main() 114 115 { 116 117 cin>>cas; 118 119 for(;cas;cas--) 120 121 { 122 123 cin>>w>>h>>n; 124 125 int cnt1=0; 126 127 for(int i=1;i<=n;i++) 128 129 { 130 131 double x,y,vx,vy; 132 133 cin>>x>>y>>vx>>vy; 134 135 l=0;r=oo; 136 137 getVAL(x,vx,w); 138 139 getVAL(y,vy,h); 140 141 if (l>=r) continue; 142 143 //保证区间有意义 144 145 event[cnt1++]=(Event){1,l}; 146 147 event[cnt1++]=(Event){2,r}; 148 149 } 150 151 sort(event,event+cnt1); 152 153 int add=0,ans=0; 154 155 for(int i=0;i<cnt1;i++) 156 157 { 158 159 if (event[i].lor==1) add++;else add--; 160 161 ans=max(ans,add); 162 163 } 164 165 cout<<ans<<endl; 166 167 } 168 169 return 0; 170 171 }
|
【关键词】:物理模型,边界处理 |
相关文章
- 10-30用CSS来实现一些动画在vue中使用之流星滑过(3)
- 10-30流星雨
- 10-30css流星雨
- 10-30流星雨
- 10-30AI怎么做流星效果? ai绘制矢量流星效果的教程
- 10-30CorelDRAW实例教程:绘制随风飘舞的花瓣和月圆之夜飞逝的流星
- 10-30Photoshop 制作简单的流星雨壁纸教程
- 10-30Photoshop入门:火流星快速下坠效果
- 10-30photoshop合成制作出流星撞击星球的壮观景象
- 10-30Photoshop设计制作非常梦幻的彩色潮流星云字