این مسابقه در تاریخ پنج شنبه ۱۴ دی به صورت حضوری در سایت دانشکده برق و کامپیوتر دانشگاه تهران برگزار شد.

J- Solar Eclipse


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

A new Solar Eclipse is going to happen on Mars. Scientists from different parts of the world are traveling to Mars to watch and study this phenomenon. You just managed to calculate exactly the best point of Mars lands for your study of the eclipse, and want to land your flying saucer at that place. But, you notice that there are already other spacecrafts landed near that area.

In the bird’s-eye view, all the spacecrafts (including yours) are circles with a constant radius RR. Logically, you hate to land your spacecraft on the others (no intersection of areas is allowed, but touching the other crafts is acceptable), though, the other saucers did not obey this rule on their own landings (i.e. their circles might have positive-area intersections with each other). In order to land your own craft on Mars, you want to find the place that minimizes the distance between the center of your flying saucer and your already calculated best point (and obeys the no-intersection rule). That’s what you should do in this problem.

input🔗

The input has multiple test cases. Each test case starts with a line containing an integer nn (number of already landed spacecrafts), and a real number rr.The land is small enough for us to be modeled by a two-dimensional plane, and (0,0)(0, 0) is conventionally the best point for us to land. Each of the next nn lines specifies the location of a landed flying saucer by giving two real numbers, xx and yy as the coordinates of its center. The input ends with a case of n=r=0n = r = 0 which must not be processed.

1n1001 \leq n \leq 100 0<R0 \lt R 0x,y10000 \leq |x|, |y| \leq 1000

output🔗

Write the result of the ii-th test case on the ii-th line of the output. You should just write the minimum possible distance between the center of your landed craft and the origin of the plane, rounded to exactly 6 digits after the decimal point.

example🔗

sample input 1🔗

1 1.234
2.468 0
1 2
2 2
2 1
1 1
-1 -1
0 0
Plain text

sample output 1🔗

0.000000
1.171573
1.414214
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.