کیانوش متقاضی عضویت در سازمان OC است. در آخرین روز مصاحبه، سازمان استعداد او در بازی…
- User
کیانوش متقاضی عضویت در سازمان OC است. در آخرین روز مصاحبه، سازمان استعداد او در بازی تانک ترابل را مورد بررسی قرار داده است.
در روز آخر مصاحبه، کیانوش باید مقابل مصاحبه کنندهها بازی کند و از آنها ببرد. در این بازی هر فرد باید یک تانک را کنترل کند و برای برنده شدن باید تانکهای حریفان را با شلیک از بین برد. در نسخهای از بازی که به کیانوش داده شده، زمین بازی را میتوان به شکل یک صفحه دوبعدی با ابعاد X X و Y Y تصور کرد و هر تانک به شکل یک دایره روی آن صفحه. شعاع دو تانک ممکن است فرق کند.
کیانوش با ترفندی یک گلولهی خاص بدست آورده که با انفجار آن، گلولههای ریز از سوی نقطهی انفجار به همه طرف پرتاب میشوند. کیانوش میخواهد نقطهی انفجار را طوری انتخاب کند که همهی تانکهای رقبا از بین بروند؛ پس از آن نقطه باید کل تانکهای رقبای او بطور کامل پیدا باشند. یعنی هر نیم خطی که از آن نقطه شروع میشود باید با حداکثر یک تانک برخورد داشته باشد. (ممکن است با تعدادی از آنها مماس شود.) نقطهی انتخابی نباید داخل تانکها باشد.(اما میتواند روی محیطشان قرار بگیرد.)
با ورودی گرفتن نقشهی بازی، یک نقطهی مناسب برای کیانوش را خروجی دهید ویا بگویید که چنین نقطهای وجود ندارد.
ورودی سطر اول ورودی شامل سه عدد طبیعی n n و X X و Y Y آمده است که به ترتیب برابر تعداد تانکهای رقبای کیانوش و مختصات زمین بازی هستند. در i iمین سطر از هریک از n n سطر بعدی سه عدد طبیعی به شکل x i y i r i x i y i r i آمده است که x i x i و y i y i مختصات تانک i iام و r i r i شعاع آن را نشان میدهد. دایرههای دو تانک با هم اشتراک ندارند اما ممکن است باهم مماس باشند. همهی تانکها داخل زمین بازی قرار دارند.
1 ≤ n ≤ 10 1≤n≤10
0 ≤ X , Y ≤ 1 0 4 0≤X,Y≤10 4
خروجی اگر نقطهی مورد نظر کیانوش وجود نداشت، خروجی باید تنها شامل عدد − 1 −1 شود. در غیر این صورت مختصات یکی از این نقاط را بصورت x
y x y خروجی دهید. اعداد را با بیشترین دقت ممکن خروجی دهید، پاسخ شما نباید بیشتر از 1 0 − 5 10 −5 خطا داشته باشد.
مثال ورودی نمونه ۱ 4 10 10 2 2 2 8 8 2 2 8 2 8 2 2 Plain text خروجی نمونه ۱ 5.0 5.0 Plain text ورودی نمونه ۲ 5 10 10 2 2 2 8 8 2 2 8 2 8 2 2 5 5 1 Plain text خروجی نمونه ۲ -1
- Assistant
To solve the problem of finding a suitable explosion point for Kiannoush in the Tank Trouble game, we need to carefully analyze the spatial arrangement of the tanks and determine a point from which all tanks can be destroyed without any ambiguity in targeting. Below is a step-by-step explanation of the approach and the reasoning behind it.
Problem Overview
Given a battlefield represented as a 2D grid with dimensions ( X \times Y ), there are ( n ) tanks, each represented by a circle with center coordinates ((x_i, y_i)) and radius ( r_i ). Kiannoush aims to find a point ( p = (p_x, p_y) ) such that:
-
Not Inside Any Tank: The point ( p ) should not lie inside any tank. Formally, for all tanks ( i ): [ \sqrt{(p_x - x_i)^2 + (p_y - y_i)^2} \geq r_i ]
-
Unique Targeting Direction: From point ( p ), any ray (half-line) emanating in any direction should intersect at most one tank. This ensures that each shot from ( p ) clearly targets a single tank without ambiguity.
Step-by-Step Solution
-
Identify Candidate Points:
- External Tangents: For every pair of tanks, compute the external tangent lines. These lines touch both tanks without intersecting the line segment connecting the centers of the tanks.
- Intersection Points: The intersection points of these external tangent lines are potential candidates for ( p ). These points are critical because they represent positions from which each pair of tanks can be uniquely targeted without overlapping visibility.
-
Validate Candidate Points: For each candidate point ( p ):
-
Check Tank Overlap: Ensure ( p ) is not inside any tank.
-
Angular Interval Calculation:
- For each tank, calculate the angle ( \theta_i ) from ( p ) to the center of the tank.
- Determine the angular range ( \Delta_i ) that the tank spans from ( p )'s perspective: [ \Delta_i = \arcsin\left(\frac{r_i}{d_i}\right) ] where ( d_i ) is the distance from ( p ) to the center of the tank ( i ).
- The tank occupies the angular interval ([ \theta_i - \Delta_i, \theta_i + \Delta_i ]).
-
Check for Overlapping Intervals: Sort all angular intervals and verify that no two intervals overlap. If any overlap is found (excluding cases where intervals only touch tangentially), ( p ) is invalid because it would mean ambiguity in targeting.
-
-
Output the Result:
- Valid Point Found: If a valid ( p ) is found that satisfies both conditions, output its coordinates with high precision.
- No Valid Point: If no such point exists, output
-1.
Handling Edge Cases
-
Tangent Points: If a candidate point lies exactly on the boundary of a tank (i.e., ( \sqrt{(p_x - x_i)^2 + (p_y - y_i)^2} = r_i )), it is still considered valid as per the problem statement.
-
Minimal Number of Tanks: When there's only one tank, any point outside that tank is valid.
-
Multiple Overlapping Tangents: In scenarios where multiple tangent lines intersect at a single point, ensure that the overlapping angles are correctly identified and handled.
Sample Inputs and Outputs
Sample Input 1:
4 10 10 2 2 2 8 8 2 2 8 2 8 2 2Sample Output 1:
5.0 5.0Explanation: The point ((5.0, 5.0)) is equidistant from all four tanks and lies outside all of them. From this point, any direction targets exactly one tank without any overlap.
Sample Input 2:
5 10 10 2 2 2 8 8 2 2 8 2 8 2 2 5 5 1Sample Output 2:
-1Explanation: The additional tank at ((5, 5)) with radius (1) blocks the previously valid point ((5.0, 5.0)), and there is no other point on the battlefield that satisfies the unique targeting condition for all tanks.
Conclusion
By systematically identifying candidate points through the computation of external tangents and validating each point against the problem's constraints, we can determine a suitable explosion point or conclude that no such point exists.
-