首页 > ACM题库 > HDU-杭电 > HDU 4189-Cybercrime Donut Investigation[解题报告]HOJ
2015
05-23

HDU 4189-Cybercrime Donut Investigation[解题报告]HOJ

Cybercrime Donut Investigation

问题描述 :

Year 2042. The Internet has evolved to a virtual reality dataspace where crimes are committed every day. The 2041 SWERC winner developed an agent that drops a donut every time a crime is committed in the Cyberspace. Each of the donuts has its own signature. The Madrid Police have a huge database with crimes and their donut signatures.
Today is your day. Your task is to implement a new agent that looks for the records in the database that bear a strong resemblance to the given signature of a dropped donut found at a new crime scene.
Coin Collecting

Figure 2: The major piece of evidence for today’s unsolved crime streak

Experts in virtual criminology have obtained the best similarity measure between donuts: compute the diff erence in radius of the internal part of the toroids (holes), compute the di fference in radius of the external part of the toroids (tubes), and then add up those di fferences.

输入:

The fi rst line of each test case contains n (1<=n<=100,000), the number of donuts in the database. The ith of the following n lines contains the radius of the hole and radius of the tube of the ith donut in the database, described by two integers l and w (1<=l,w<=109). After that there is a line containing q
(1<=q<=50,000), the number of donuts that you are looking for in the database. Then q lines follow, the ith of them describing the dimensions of the newly found ith donut in the same way.
Diff erent test cases are separated by a blank line. A line containing -1 marks the end of the input.

输出:

The fi rst line of each test case contains n (1<=n<=100,000), the number of donuts in the database. The ith of the following n lines contains the radius of the hole and radius of the tube of the ith donut in the database, described by two integers l and w (1<=l,w<=109). After that there is a line containing q
(1<=q<=50,000), the number of donuts that you are looking for in the database. Then q lines follow, the ith of them describing the dimensions of the newly found ith donut in the same way.
Diff erent test cases are separated by a blank line. A line containing -1 marks the end of the input.

样例输入:

2
2 3
3 4
2
1 1
3 4

2
1 1
9 9
4
4 5
6 5
2 5
3 4

-1

样例输出:

3
0

7
7
5
5

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define VI vector<int>
#define pii pair<int,int>
#define LL __int64
#define DB double
using namespace std;
const int MAXN = 200100;
//const LL INF = 0x3f3f3f3f3f3f3f3fL;
LL INF;
const int MOD = 1e9 + 7;
const double eps = 1e-10;
int n,m,topx,topy;
struct Point{
    LL x,y,id;
}p[MAXN],q[MAXN];
map<LL,LL> xid,yid;
LL cntx[MAXN],cnty[MAXN];
LL tree[MAXN],Ans[MAXN];
LL lowbit(int x){
    return x & (-x);
}
void update(int x,LL val,int Limit){
    while(x <= Limit){
        tree[x] = max(tree[x],val);
        x += lowbit(x);
    }
}
LL query(int x){
    LL res = -INF;
    while(x > 0){
        res = max(tree[x],res);
        x -= lowbit(x);
    }
    return res;
}
bool cmpx(Point a,Point b){
    return a.x < b.x;
}
bool cmpy(Point a,Point b){
    return a.y < b.y;
}
void solve(){
    int k;
    sort(p,p + n,cmpx);
    sort(q,q + m,cmpx);
    memset(tree,-INF,sizeof(tree));
    k = 0;
    for(int i = 0; i < m;i++){
        while(k < n && p[k].x <= q[i].x){
            update(yid[p[k].y],p[k].x + p[k].y,topy + 1);
            k++;
        }
        LL res = query(yid[q[i].y]);
        Ans[q[i].id] = min(q[i].x + q[i].y - res,Ans[q[i].id]);
    }

    memset(tree,-INF,sizeof(tree));
    k = 0;
    for(int i = 0; i < m;i++){
        while(k < n && p[k].x <= q[i].x){
            update(topy - yid[p[k].y] + 1,p[k].x - p[k].y,topy + 1);
            k++;
        }
        LL res = query(topy - yid[q[i].y] + 1);
        Ans[q[i].id] = min(q[i].x - q[i].y - res,Ans[q[i].id]);
    }
    memset(tree,-INF,sizeof(tree));
    k = n - 1;
    for(int i = m - 1; i >= 0;i--){
        while(k >= 0 && p[k].x >= q[i].x){
            update(yid[p[k].y],p[k].y - p[k].x,topy + 1);
            k--;
        }
        LL res = query(yid[q[i].y]);
        Ans[q[i].id] = min(q[i].y - q[i].x - res,Ans[q[i].id]);
    }
    memset(tree,-INF,sizeof(tree));
    k = n - 1;
    for(int i = m - 1; i >= 0;i--){
        while(k >= 0 && p[k].x >= q[i].x){
            update(topy - yid[p[k].y] + 1,0 - (p[k].y + p[k].x),topy + 1);
            k--;
        }
        LL res = query(topy - yid[q[i].y] + 1);
        Ans[q[i].id] = min(0 - (q[i].y + q[i].x) - res,Ans[q[i].id]);
    }
}
int main()
{
    INF = 0x3f3f3f3f;
    INF = (INF << 32) + INF;
    bool flag = false;
    while(scanf("%d",&n) != EOF){
        if(n == -1) break;
        if(flag) printf("\n");
        else flag = true;
        topx = topy = 0;
        for(int i = 0; i < n;i++){
            scanf("%I64d%I64d",&p[i].x,&p[i].y);
    //        cntx[topx++] = p[i].x;
            cnty[topy++] = p[i].y;
        }
        scanf("%d",&m);
        for(int i = 0; i < m;i++){
            scanf("%I64d%I64d",&q[i].x,&q[i].y);
            q[i].id = i;
      //      cntx[topx++] = q[i].x;
            cnty[topy++] = q[i].y;
        }
  //      sort(cntx,cntx + topx);
        sort(cnty,cnty + topy);
  //      topx = unique(cntx,cntx + topx) - cntx;
        topy = unique(cnty,cnty + topy) - cnty;
   //     xid.clear();
        yid.clear();
   //     for(int i = 1; i <= topx; i++)
   //         xid[cntx[i-1]] = i;
        for(int i = 1; i <= topy; i++)
            yid[cnty[i-1]] = i;
        memset(Ans,INF,sizeof(Ans));
        solve();
        for(int i = 0; i < m; i++)
            printf("%I64d\n",Ans[i]);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/oppsitre/article/details/17148923


  1. 总是以为自己放下了。可是好久了,也知道他已经有了另一个她,却无论如何总是无法不去关注有关他的一切。微博,空间,网站。总希望从那些地方找到有关他的只言片语。手机号删了,却一样可以背出那11位数。删掉他的Q。可是另一个Q却依然留着。写了好多有关他的文,但是,

  2. 总是以为自己放下了。可是好久了,也知道他已经有了另一个她,却无论如何总是无法不去关注有关他的一切。微博,空间,网站。总希望从那些地方找到有关他的只言片语。手机号删了,却一样可以背出那11位数。删掉他的Q。可是另一个Q却依然留着。写了好多有关他的文,但是,

  3. 总是以为自己放下了。可是好久了,也知道他已经有了另一个她,却无论如何总是无法不去关注有关他的一切。微博,空间,网站。总希望从那些地方找到有关他的只言片语。手机号删了,却一样可以背出那11位数。删掉他的Q。可是另一个Q却依然留着。写了好多有关他的文,但是,

  4. 总是以为自己放下了。可是好久了,也知道他已经有了另一个她,却无论如何总是无法不去关注有关他的一切。微博,空间,网站。总希望从那些地方找到有关他的只言片语。手机号删了,却一样可以背出那11位数。删掉他的Q。可是另一个Q却依然留着。写了好多有关他的文,但是,

  5. 总是以为自己放下了。可是好久了,也知道他已经有了另一个她,却无论如何总是无法不去关注有关他的一切。微博,空间,网站。总希望从那些地方找到有关他的只言片语。手机号删了,却一样可以背出那11位数。删掉他的Q。可是另一个Q却依然留着。写了好多有关他的文,但是,

  6. 总是以为自己放下了。可是好久了,也知道他已经有了另一个她,却无论如何总是无法不去关注有关他的一切。微博,空间,网站。总希望从那些地方找到有关他的只言片语。手机号删了,却一样可以背出那11位数。删掉他的Q。可是另一个Q却依然留着。写了好多有关他的文,但是,

  7. 嗯,我也跟你一样,我怜美喜欢,瑶瑶也喜欢,她们都是有苦中的啊,比如怜美曾经是那么纯真的美丽女孩,被玷污了,黑化了;瑶瑶也是个纯真的女孩,被误会了,被爱情伤害了。她们都是被爱情所困啊,就算怜美做的很过分,那也是应为她喜欢男主。所以,瑶瑶党和怜美党别骂了,瑶

  8. 嗯,我也跟你一样,我怜美喜欢,瑶瑶也喜欢,她们都是有苦中的啊,比如怜美曾经是那么纯真的美丽女孩,被玷污了,黑化了;瑶瑶也是个纯真的女孩,被误会了,被爱情伤害了。她们都是被爱情所困啊,就算怜美做的很过分,那也是应为她喜欢男主。所以,瑶瑶党和怜美党别骂了,瑶

  9. 嗯,我也跟你一样,我怜美喜欢,瑶瑶也喜欢,她们都是有苦中的啊,比如怜美曾经是那么纯真的美丽女孩,被玷污了,黑化了;瑶瑶也是个纯真的女孩,被误会了,被爱情伤害了。她们都是被爱情所困啊,就算怜美做的很过分,那也是应为她喜欢男主。所以,瑶瑶党和怜美党别骂了,瑶

  10. 嗯,我也跟你一样,我怜美喜欢,瑶瑶也喜欢,她们都是有苦中的啊,比如怜美曾经是那么纯真的美丽女孩,被玷污了,黑化了;瑶瑶也是个纯真的女孩,被误会了,被爱情伤害了。她们都是被爱情所困啊,就算怜美做的很过分,那也是应为她喜欢男主。所以,瑶瑶党和怜美党别骂了,瑶

  11. 嗯,我也跟你一样,我怜美喜欢,瑶瑶也喜欢,她们都是有苦中的啊,比如怜美曾经是那么纯真的美丽女孩,被玷污了,黑化了;瑶瑶也是个纯真的女孩,被误会了,被爱情伤害了。她们都是被爱情所困啊,就算怜美做的很过分,那也是应为她喜欢男主。所以,瑶瑶党和怜美党别骂了,瑶

  12. 嗯,我也跟你一样,我怜美喜欢,瑶瑶也喜欢,她们都是有苦中的啊,比如怜美曾经是那么纯真的美丽女孩,被玷污了,黑化了;瑶瑶也是个纯真的女孩,被误会了,被爱情伤害了。她们都是被爱情所困啊,就算怜美做的很过分,那也是应为她喜欢男主。所以,瑶瑶党和怜美党别骂了,瑶

  13. 嗯,我也跟你一样,我怜美喜欢,瑶瑶也喜欢,她们都是有苦中的啊,比如怜美曾经是那么纯真的美丽女孩,被玷污了,黑化了;瑶瑶也是个纯真的女孩,被误会了,被爱情伤害了。她们都是被爱情所困啊,就算怜美做的很过分,那也是应为她喜欢男主。所以,瑶瑶党和怜美党别骂了,瑶

  14. 嗯,我也跟你一样,我怜美喜欢,瑶瑶也喜欢,她们都是有苦中的啊,比如怜美曾经是那么纯真的美丽女孩,被玷污了,黑化了;瑶瑶也是个纯真的女孩,被误会了,被爱情伤害了。她们都是被爱情所困啊,就算怜美做的很过分,那也是应为她喜欢男主。所以,瑶瑶党和怜美党别骂了,瑶

  15. 嗯,我也跟你一样,我怜美喜欢,瑶瑶也喜欢,她们都是有苦中的啊,比如怜美曾经是那么纯真的美丽女孩,被玷污了,黑化了;瑶瑶也是个纯真的女孩,被误会了,被爱情伤害了。她们都是被爱情所困啊,就算怜美做的很过分,那也是应为她喜欢男主。所以,瑶瑶党和怜美党别骂了,瑶

  16. 嗯,我也跟你一样,我怜美喜欢,瑶瑶也喜欢,她们都是有苦中的啊,比如怜美曾经是那么纯真的美丽女孩,被玷污了,黑化了;瑶瑶也是个纯真的女孩,被误会了,被爱情伤害了。她们都是被爱情所困啊,就算怜美做的很过分,那也是应为她喜欢男主。所以,瑶瑶党和怜美党别骂了,瑶

  17. 嗯,我也跟你一样,我怜美喜欢,瑶瑶也喜欢,她们都是有苦中的啊,比如怜美曾经是那么纯真的美丽女孩,被玷污了,黑化了;瑶瑶也是个纯真的女孩,被误会了,被爱情伤害了。她们都是被爱情所困啊,就算怜美做的很过分,那也是应为她喜欢男主。所以,瑶瑶党和怜美党别骂了,瑶

  18. 嗯,我也跟你一样,我怜美喜欢,瑶瑶也喜欢,她们都是有苦中的啊,比如怜美曾经是那么纯真的美丽女孩,被玷污了,黑化了;瑶瑶也是个纯真的女孩,被误会了,被爱情伤害了。她们都是被爱情所困啊,就算怜美做的很过分,那也是应为她喜欢男主。所以,瑶瑶党和怜美党别骂了,瑶