Covid Statistics


Submit solution

Points: 25
Time limit: 4.0s
Memory limit: 256M

Author:
Problem type

You are given \(N\) countries represented as 2D disks with a center \((X, Y)\) and a radius \(R\),

and \(M\) cities represented as points with coordinates \((X, Y)\) and \(C\) the number of Covid 19 confirmed cases in this city.

You mission is to find the country with the highest number of confirmed cases.

If multiple countries have the same highest number of confirmed cases, choose the one with the higher density (confirmed cases by area), and if it still equality, choose the country that listed first.

Input Specification

The first line contains an integer \(1\le T \le 10\), the number of test cases.

The first line of each test case contains \(1 \le N, M \le 1000\) separated by a space.

Then N lines follow, each line gives a string and 3 integers \(1 \le X, Y, R \le 1000\) separated by spaces, representing respectively the name of the country, its coordinates and its radius.

Then M lines follow, each line gives 3 integers \(1 \le X, Y, C \le 1000\) separated by spaces, representing the coordinates of a city and the number of its confirmed cases.

The length of country names doesn't exceed 20 characters.

Output Specification

The name of the country we are looking for. One line per test case.

Sample Input

2
2 3
CHOVINDA 2 2 1
USAVIDA 5 5 2
2 1 10
1 2 11
5 4 20
3 5
CHOVINDA 2 2 2
USAVIDA 6 6 1
CLEANLAND 1000 1000 1
1 1 1
2 2 2
3 3 3
4 4 4
5 6 10

Sample Output

CHOVINDA
USAVIDA

Sample Input

1
2 2
A 1 1 1
B 1 2 1
3 1 1
3 2 2

Sample Output

A

Notes

  • Countries may overlap.

  • The boundary circle of a country is part of it.

  • The name of a country is formed only from English uppercase letters.

  • A city can belong to 0, 1 or multiple countries.

  • Number of infected cases should be added to all countries of the city.


Comments


  • 0
    AkramElOmrani  commented on July 10, 2021, 8:28 p.m.

    Can the density be a float ?