UVALive3905 流星

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=283&page=show_problem&problem=1906

【题目描述】：在夜空下，放置一个摄像头，已知，摄像头左下角在（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 }

【关键词】：物理模型，边界处理