题解引自:http://www.cnblogs.com/wuyiqi/archive/2012/04/28/2474614.html
这题和着题解一块看,看了半天才看懂的....菜菜....
题意：有一排的枪编号依次为1~n 有一排靶子编号依次为1~m
告诉你哪些枪能打中哪些靶子，然后如果每次只能选连续的P把枪，连续的Q个靶子，每次能打中的靶子的最大值为多少
答案是把每次打中的最大值相加再除以总的次数
即选择 1~P 的枪能打中的最多的靶子的数量 + 2~p+1 的枪能打中的最多的靶子的数量 +。。。n-p+1~n的枪能打中的最多的靶子的数量 /（n-p+1）
注意，每把枪最多只能打一个靶子
解法：将题目中的关系转换为坐标 以枪为纵坐标 a 能打中 b ，在坐标系中为（b，a），然后连续的P把枪和连续的Q个靶子则可以表示为
用一个P x Q的矩形去覆盖，最多能覆盖的总的点数，就是poj 2482 了，但要注意一点，如果两根同一高度的水平线的距离小于Q，则重叠的部分职能算一次，因为每把枪只能打一个靶子
// File Name: 3597.cpp // Author: Zlbing // Created Time: 2013/7/21 14:25:06 #include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<cmath> #include<queue> using namespace std; #define CL(x,v); memset(x,v,sizeof(x)); #define INF 0x3f3f3f3f #define LL long long #define REP(i,r,n) for(int i=r;i<=n;i++) #define RREP(i,n,r) for(int i=n;i>=r;i--) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int MAXN=5e4+100; struct point{ int x,y; bool operator <(const point& rsh)const{ if(y==rsh.y)return x<rsh.x; else return y<rsh.y; } }G[100050]; int sum[MAXN<<2]; int col[MAXN<<2]; void pushup(int rt) { sum[rt]=max(sum[rt<<1],sum[rt<<1|1]); } void pushdown(int rt) { if(col[rt]) { sum[rt<<1]+=col[rt]; sum[rt<<1|1]+=col[rt]; col[rt<<1]+=col[rt]; col[rt<<1|1]+=col[rt]; col[rt]=0; } } void update(int L,int R,int flag,int l,int r,int rt) { if(L<=l&&R>=r) { col[rt]+=flag; sum[rt]+=flag; return; } pushdown(rt); int m=(l+r)>>1; if(L<=m)update(L,R,flag,lson); if(R>m)update(L,R,flag,rson); pushup(rt); } int main() { int T; scanf("%d",&T); while(T--) { int n,m,p,q,K; scanf("%d%d%d%d",&n,&m,&p,&q); scanf("%d",&K); for(int i=0;i<K;i++) { scanf("%d%d",&G[i].y,&G[i].x); } sort(G,G+K); int ans=0; int j=0,k=0; CL(sum,0); CL(col,0); for(int i=1;i+p-1<=n;i++) { for(;G[j].y-i<p&&j<K;j++) { if(j+1<K&&G[j].y==G[j+1].y&&G[j+1].x-G[j].x<q) update(G[j].x,G[j+1].x-1,1,1,m,1); else update(G[j].x,min(m,G[j].x+q-1),1,1,m,1); } ans+=sum[1]; for(;k<j&&G[k].y==i;k++) { if(k+1<j&&G[k].y==G[k+1].y&&G[k+1].x-G[k].x<q) update(G[k].x,G[k+1].x-1,-1,1,m,1); else update(G[k].x,min(m,G[k].x+q-1),-1,1,m,1); } } printf("%.2lf ",(double)ans/(n-p+1)); } return 0; }