uvalive3905Meteor

题意：给你一个矩形照相机，还有n个流星的初始位置和速度，求能找到流星最多的时刻，注意，在相机边界上的点不会被照到。

$\epsfbox{p3905.eps}$

分析：相机的边界是固定的，只需要判断每一颗流星是否在照相机的区域内出现过，如果出现过，记录其出现的时间区间[ai,bi],那么问题转化为求一个时间t使得此时有最多的区间经过这个点，类似于“扫描线”

View Code

 1 #include <stdio.h>
 2 #include <algorithm>
 3 using namespace std;
 4 #define DEBUG
 5 double max(double a, double b){
 6     return a>b?a:b;
 7 }
 8 double min(double a, double b){
 9     return a<b?a:b;
10 }
11 int max(int a, int b){
12     return a>b?a:b;
13 }
14 void update(int x, int a, int w, double& L, double& R){
15     if(a==0){
16         if(x<=0||x>=w) R=L-1;
17     }else if(a>0){
18         L = max(L, -x*1.0/a);
19         R = min(R, (w-x)*1.0/a);
20     }else{
21         L = max(L, (w-x)*1.0/a);
22         R = min(R, -x*1.0/a);
23     }
24 }
25 
26 const int MAXN = 100000 + 10;
27 
28 struct ZZ{
29     double x;
30     int type;        //0表示←，1表示→
31     bool operator < (const ZZ&z) const{
32         return x<z.x || (x==z.x && type>z.type);
33     }
34 };
35 ZZ zz[MAXN*2];
36 
37 int main(){
38 #ifndef DEBUG
39     freopen("in.txt", "r", stdin);
40 #endif
41     int cas;
42     scanf("%d", &cas);
43     while(cas--){
44         int w, h, n, e=0;
45         scanf("%d%d%d", &w, &h, &n);
46         int i;
47         for(i=0; i<n; i++){
48             int a, b, x, y;
49             scanf("%d%d%d%d", &x, &y, &a, &b);
50             double L = 0, R = 1e9;
51             update(x, a, w, L, R);
52             update(y, b, h, L, R);
53             if(R>L){
54                 ZZ tz;
55                 tz.x = L;
56                 tz.type = 0;
57                 zz[e++] = tz;
58                 tz.x = R;
59                 tz.type = 1;
60                 zz[e++] = tz;
61             }
62         }
63         sort(zz, zz+e);
64         int cnt=0, ans=0;
65         for(i=0; i<e; i++){
66             if(zz[i].type==0) ans=max(ans, ++cnt);
67             else cnt--;
68         }
69         printf("%d\n", ans);
70     }
71     return 0;
72 }

update()中当a>0时L=max（L, -x*1.0/a)包括了x取正和取负两种情况

Greatness is never a given, it must be earned.