Solution:
记一颗流星在视野内的时间段为(L, R），
为了使所有(L, R)都取整数，首先将坐标放大。
放大倍数可取为
LCM(1, 2, ..., 10）= 2520
接着计算：从0时刻开始，每单位时间内入画的流星数，即数组：
a[0], ..., a[M]
显然这可借助线段树，但难免繁琐。
考虑到这道题区间操作的特殊性：每次对区间[L, R)内的元素加一，用差分序列更方便。
数组a[0...M]的差分序列d[0...M]定义为：
d[0]=a[0],
d[i]=a[i]-a[i-1], i>0
对于这道题，我们只要维护数组a[ ]的差分序列d[ ]即可。
------------------------------------------------------------------------------------
Implementation:
当然可以先离散化，但下面的实现用map (also called "asscociated array") 避免离散化:
#include <bits/stdc++.h>
using namespace std; const int N=1e5+;
const int INF=0x3f3f3f3f; int x[N], y[N], a[N], b[N], t[N][];
int n, w, h; map<int,int> mp;
//! Repeating
void get_t(int i){
int tx1, tx2, ty1, ty2;
if(a[i]==){
if(x[i]> && x[i]<w){
tx1=;
tx2=INF;
}
else{
tx1=tx2=;
}
}
else{
tx1=-x[i]/a[i];
tx2=(w-x[i])/a[i];
}
if(b[i]==){
if(y[i]> && y[i]<h){
ty1=;
ty2=INF;
}
else{
ty1=ty2=;
}
}
else{
ty1=-y[i]/b[i];
ty2=(h-y[i])/b[i];
}
t[i][]=max(min(tx1, tx2), min(ty1, ty2));
t[i][]=min(max(tx1, tx2), max(ty1, ty2));
t[i][]=max(t[i][], );
if(t[i][]>t[i][]){
mp[t[i][]+]++;
mp[t[i][]]--;
}
} int main(){
int T;
for(cin>>T; T--; mp.clear()){
cin>>w>>h>>n;
w*=;
h*=;
mp[];
for(int i=; i<n; i++){
cin>>x[i]>>y[i]>>a[i]>>b[i];
x[i]*=, y[i]*=;
get_t(i);
}
// As with any other type specifier, we can define mutiple variables using auto.
// Because a declaratin can involve only a single base type, the initializers for all the
// variables in the declaration must have types that are consistent with each other.
int ans =;
// tedious
auto i=mp.begin(), j=i;
++j; for(; j!=mp.end(); ++i, ++j){
j->second+=i->second;
ans=max(ans, j->second);
}
cout << ans <<'\n';
} return ;
}
代码写得很差劲：
- 重复,不符合 Keep DRY (Don't Repeat Yourself）原则
- 所有的数组其实都不需要开
- 计算前项和（prefix sum)过于繁琐，显得很笨 (dull)
---------------------------------------------------------------------------------------
总之丑得看不下去了，代码写成这样，和咸鱼有什么区别。。。。。
Enhanced:
#include <bits/stdc++.h>
using namespace std; const int N=1e5+;
const int INF=0x3f3f3f3f;
int x, y, a, b;
int n, w, h; map<int,int> mp; void get_t(int &L, int &R, int v, int p, int b){
if(v){
L=max(L, min(-p/v, (b-p)/v));
R=min(R, max(-p/v, (b-p)/v));
}
else if(p<= || p>=b) R=L;
} int main(){
ios::sync_with_stdio(false); int T;
for(cin>>T; T--; mp.clear()){
cin>>w>>h>>n;
w*=;
h*=; for(int i=, L, R; i<n; i++){
cin>>x>>y>>a>>b;
x*=, y*=;
L=, R=INF;
get_t(L, R, a, x, w);
get_t(L, R, b, y, h); if(R>L)
mp[L]++, mp[R]--;
}
int ans =, sum=; for(auto i:mp){
sum+=i.second;
ans=max(sum, ans);
}
cout << ans <<'\n';
}
return ;
}
-----------------------------------------------
还有一种更为美妙的实现：
#include <bits/stdc++.h>
using namespace std; const int N=1e5+;
const int INF=0x3f3f3f3f;
int x, y, a, b;
int n, w, h; vector<pair<int,int>> vec; //Don't repeat yourself. (keep DRY) void get_t(int &L, int &R, int v, int p, int b){
if(v){
L=max(L, min(-p/v, (b-p)/v));
R=min(R, max(-p/v, (b-p)/v));
}
else if(p<= || p>=b) R=L;
} int main(){
ios::sync_with_stdio(false); int T;
for(cin>>T; T--; ){
cin>>w>>h>>n;
w*=;
h*=; vec.clear(); for(int i=, L, R; i<n; i++){
cin>>x>>y>>a>>b;
x*=, y*=;
L=, R=INF;
get_t(L, R, a, x, w);
get_t(L, R, b, y, h);
if(R>L){ //error-prone
vec.push_back({L, });
vec.push_back({R, -});
}
}
sort(vec.begin(), vec.end());
int ans =, sum=; for(auto i:vec){
sum+=i.second;
ans=max(sum, ans);
}
cout << ans <<'\n';
} return ;
}
言不尽意，读者自己欣赏吧。。。。。。。。。