题目链接：http://acm.hnu.cn/online/?action=problem&type=show&id=12033
题意：给定一个n*m 的方格，num个污染源及坐标。(x,y)污染程度：min(max(|x-xi|, |y − yi|))，(xi,yi)表示污染源的坐标。现在对n*m-num个格子编号。首先按污染程度,x,y的优先级编号，越小编号越大。现在有q个询问，每次询问编号为k的坐标(x,y)
解题思路：三次二分,先二分k所对应的污染程度，对于确定的污染程度dis可以用矩形的面积并求出<=dis的有多少个。求出dis后在二分x，之后二分y，求出的x，y即为答案。
#include<iostream>
#include<stdio.h>
#define LL long long
#define N 105
const LL inf=(LL)1e9+10;
using namespace std;
struct point{
LL x,y;
point(LL x=0,LL y=0):x(x),y(y){}
void read(){ cin>>x>>y; }
}p[N];
struct rec
{
point p1,p2;
rec(point _=point(),point __=point()):p1(_),p2(__){}
rec(LL x1,LL y1,LL x2,LL y2):p1(point(x1,y1)),p2(point(x2,y2)){}
void get(LL &x1,LL &y1,LL &x2,LL &y2){
x1=p1.x; y1=p1.y; x2=p2.x; y2=p2.y;
}
LL area(point p3=point(inf,inf)){
return (min(p2.x,p3.x)-min(p1.x,p3.x))*(min(p2.y,p3.y)-min(p1.y,p3.y));
}
}r1[N],r2[N],tmp[N];
LL cnt1,cnt2,tcnt,n,m,num;
inline void cut(rec a,rec b,rec r[],LL &cnt)
{//其中点分别为矩形左下侧点和右上侧点
LL k1,k2,k3,k4,x1,x2,x3,x4,y1,y2,y3,y4;
a.get(x1,y1,x2,y2); b.get(x3,y3,x4,y4);
if(x2<=x3||y2<=y3||x4<=x1||y4<=y1){
r[cnt++]=rec(x1,y1,x2,y2);//如果不相交
return ;
}
k1=max(x1,x3);k2=min(x2,x4);
if(x1<k1) r[cnt++]=rec(x1,y1,k1,y2);
if(x2>k2) r[cnt++]=rec(k2,y1,x2,y2);
k3=k1,k4=k2;
k1=max(y1,y3);k2=min(y2,y4);
if(y1<k1) r[cnt++]=rec(k3,y1,k4,k1);
if(y2>k2) r[cnt++]=rec(k3,k2,k4,y2);
}
LL get_num(rec r[],LL cnt,point p=point(inf,inf))
{
LL ret=0;
for(int i=0;i<cnt;i++)
ret=ret+r[i].area(p);
return ret;
}
void get_rec(LL dis,rec r[],LL &cnt)
{
cnt=0;
for(int i=0;i<num;i++)
{
for(int j=0;j<cnt;j++) tmp[j]=r[j];
tcnt=cnt; cnt=0;
rec rr=rec(max(p[i].x-dis,1ll),max(p[i].y-dis,1ll),min(p[i].x+dis,n)+1,min(p[i].y+dis,m)+1);
for(int j=0;j<tcnt;j++) cut(tmp[j],rr,r,cnt);
r[cnt++]=rr;
}
}
void solve(LL k)
{
LL x,y,l,r,mid;
l=1; r=max(n,m);
while(l<r){
mid=(l+r)/2;
get_rec(mid,r1,cnt1);
if(get_num(r1,cnt1)<k) l=mid+1;
else r=mid;
}
get_rec(l,r1,cnt1);
get_rec(l-1,r2,cnt2);
k-=get_num(r2,cnt2);
point p;
l=1; r=n+1;
while(l<r){
mid=(l+r)/2;
p=point(mid,inf);
if(get_num(r1,cnt1,p)-get_num(r2,cnt2,p)<k) l=mid+1;
else r=mid;
}
x=l; l=1; r=m+1;
p=point(x-1,inf);
k-=(get_num(r1,cnt1,p)-get_num(r2,cnt2,p));
while(l<r){
mid=(l+r)/2;
p=point(x,mid);
LL tmp=get_num(r1,cnt1,p)-get_num(r2,cnt2,p);
p=point(x-1,mid);
tmp-=get_num(r1,cnt1,p)-get_num(r2,cnt2,p);
if(tmp<k) l=mid+1;
else r=mid;
}
y=l;
cout<<x-1<<' '<<y-1<<endl;
}
int main()
{
// freopen("1.in","r",stdin);
while(cin>>n>>m>>num,n+m+num)
{
for(int i=0;i<num;i++) p[i].read();
LL q,k;
cin>>q;
while(q--)
{
cin>>k;
solve(k+num);
}
puts("-");
}
}
// by oone
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
#define D 2
struct cube{
int s[D],e[D];
int type;
cube(){}
cube(cube &t,int m,int type):type(type){
for(int i=0;i<D;i++){
s[i]=t.s[i]-m;
e[i]=t.e[i]+m;
}
}
LL area(cube &t){
LL k=1;
for(int i=0;i<D;i++)
k*=(LL)(min(e[i],t.e[i])-max(s[i],t.s[i]));
return k;
}
}p[30],big;
cube c[1000],d[1000];
int q;
struct CUT{
int cn,dn;
void broke(cube &a,cube &b){
cube t;
for(int i=0;i<D;i++){
if(b.s[i]>a.s[i]&&b.s[i]<a.e[i]){
t=a;
t.e[i]=b.s[i];
d[dn++]=t;
a.s[i]=b.s[i];
}
if(b.e[i]>a.s[i]&&b.e[i]<a.e[i]){
t=a;
t.s[i]=b.e[i];
d[dn++]=t;
a.e[i]=b.e[i];
}
}
}
bool check(cube &a,cube &b){
for(int i=0;i<D;i++)
if(a.s[i]>=b.e[i]||b.s[i]>=a.e[i])return 0;
return 1;
}
void insert(cube &t){
dn=0;
for(int i=0;i<cn;i++){
if(check(c[i],t))broke(c[i],t);
else d[dn++]=c[i];
}
cn=0;
c[cn++]=t;
for(int i=0;i<dn;i++)c[cn++]=d[i];
}
void push(int m,int type){
for(int i=0;i<q;i++){
cube t(p[i],m,type);
insert(t);
}
}
LL area(cube &t){
LL ans=0;
for(int i=0;i<cn;i++)
if(check(c[i],t))ans+=c[i].area(t);
return ans;
}
void refush(){
int n=0;
for(int i=0;i<cn;i++)
if(c[i].type)c[n++]=c[i];
cn=n;
}
}cut;
void solve(){
LL n;
cin>>n;
int l=0,r=max(big.e[0],big.e[1]);
while(l<r){
cut.cn=0;
int m=(l+r)>>1;
cut.push(m,1);
if(cut.area(big)-q<n)l=m+1;
else r=m;
}
cut.cn=0;
cut.push(l-1,1);
n-=(cut.area(big)-q);
cut.cn=0;
cut.push(l,1);
cut.push(l-1,0);
cut.refush();
cube res=big;
l=0,r=big.e[1];
while(l<r){
res.e[1]=(l+r)>>1;
if(cut.area(res)<n)l=res.e[1]+1;
else r=res.e[1];
}
res.e[1]=l-1;
n-=cut.area(res);
res.s[1]=l-1;
res.e[1]=l;
l=0,r=big.e[0];
while(l<r){
res.e[0]=(l+r)>>1;
if(cut.area(res)<n)l=res.e[0]+1;
else r=res.e[0];
}
printf("%d %d\n",res.e[1],l);
}
int main(){
while(scanf("%d%d%d",&big.e[1],&big.e[0],&q),big.e[0]||big.e[1]||q){
big.s[0]=big.s[1]=0;
for(int i=0;i<q;i++){
for(int j=D-1;j>=0;j--){
scanf("%d",&p[i].e[j]);
p[i].s[j]=p[i].e[j]-1;
}
}
int Q;
scanf("%d",&Q);
while(Q--)solve();
puts("-");
}
return 0;
}