2 shunfurh shunfurh 于 2017.01.12 23:47 提问

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 difference in radius of the internal part of the toroids (holes), compute the difference in radius of the external part of the toroids (tubes), and then add up those differences. 

输入:

The first 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.
Different test cases are separated by a blank line. A line containing -1 marks the end of the input.
输出:

The first 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.
Different 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

1个回答

caozhy
caozhy   Ds   Rxr 2017.01.12 23:53
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!