511 - Do You Know the Way to San Jose?

[damnerd]

Anyone knows what's the largest number of maps and or cities? i.e. the limits on the size of each test case?

[stubbscroll]

I'm stuck on this problem, and I can't even get the example right. Could someone tell me where I'm wrong here (or verify that the example is wrong)?

In the second query (San Francisco, level 2), there are three eliglble maps:

Level 1: NCalif, area 572, distance to center sqrt(121.16)
Level 2: SanMateo, area 35, distance to center sqrt(5.41)
Level 3: BayArea, area 35, distance to center sqrt(2.26)

BayArea has a shorter distance to center, so this would make it more preferrable than SanMateo since they both have equal area. However, the correct answer according to the sample output is BayArea.

Have I missed some crucial details, or is this yet another broken problem? This problem wasn't submittable before the migration.

Anyone knows what's the largest number of maps and or cities? i.e. the limits on the size of each test case?

My program using static arrays doesn't crash when assuming 5000 maps, 5000 locations and a maximal name length of 139.

[brianfry713]

I agree with your logic that the sample output seems wrong. I got AC on this problem by simply doing a qsort on the area of each map containing that city and ignoring the rest. So my code doesn't consider whether multiple maps have the same area, the distance to center, aspect ratio, distance to the lower right corner, or the smallest x-coordinate. My code matches the sample I/O.

I can confirm that 5000 maps, 5000 locations and a maximal name length of 139 are large enough assumptions.

[stubbscroll]

Thanks for the info, Brian! Seems like this problem could use a new dataset...

[cksteven]

i tried and fixed some problems i found but i still got WA.
my code can pass the sample i/o data.

can anyone offer me some I/O data,plz?

or this is my code,if you are helpful and free,would you help me fix it?

Code: Select all

	......
	cout<<name<<" at detail level "<<level<<ends;
	......

[lighted]

Your output doesn't match sample. Change line

Code: Select all

cout<<name<<" at detail level "<<level<<ends;

It must be

Code: Select all

cout<<name<<" at detail level "<<level<<" ";

Don't forget to remove your code after getting accepted.

[cksteven]

Thank you very much, @lighted!
Now i knew the difference between

Code: Select all

cout<<ends;

and

Code: Select all

cout<<" ";

.
p.s. My C++ Primer (Chinese Edition) says ends will output a space.

[lighted]

printing ends will output null character '\0' not space.

[metaphysis]

The test data is not strong. For a given location, the area of every map which contains the location is distinct, so for a given level, it exists a only map or not. You even can ignore the preferred rule!