题意：给你一个矩形照相机，还有n个流星的初始位置和速度，求能找到流星最多的时刻，注意，在相机边界上的点不会被照到。
分析：相机的边界是固定的，只需要判断每一颗流星是否在照相机的区域内出现过，如果出现过，记录其出现的时间区间[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取正和取负两种情况
