跑刀仔【牛客tracker 每日一题】
跑刀仔
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
旺仔哥哥最近迷上了玩某款搜打撤游戏，但是因为他实在是太菜了，所以他只敢带一把小破刀进地图刮地皮。这款游戏里面有一个非常强劲的道具——探测器，使用探测器，可以探测到一个半径为r rr的范围内敌人的位置。实际上，很多强力的猛攻玩家经常会携带这个道具，这让旺仔哥哥总是提心吊胆，因为一旦被探测到，他基本上就可以自己找地方躺板板了。
今天，旺仔哥哥在一个l × l l×ll×l的地图里面跑刀玩，然后他就听到了一大片探测器的音效。作为站在某个重要桥上的侦察位，你自然知道这些探测器都在哪些地方被使用，具体而言，第i ii个探测器位于位置( x i , y i ) (x_i,y_i)(xi,yi)。
旺仔哥哥希望你帮他找到一个位置( x , y ) (x,y)(x,y)，使得该位置不在任何一个探测器的覆盖范围内。数据保证一定存在至少一个这样的位置。
输入描述：
输入的第一行包含两个整数n , l ( 1 ≦ n ≦ 10 ; 1 ≦ l ≦ 10 5 ) n,l (1≦n≦10; 1≦l≦10^5)n,l(1≦n≦10;1≦l≦105)n,l，分别表示探测器的个数和整个地图的大小。
此后n nn行，第i ii行输入三个正整数x i , y i , r i ( 0 ≦ x i , y i , r i ≦ l ) x_i,y_i,r_i(0≦x_i,y_i,r_i≦l)xi,yi,ri(0≦xi,yi,ri≦l)，意义如上所述。
输出描述：
如果可以找到，输出两个数x , y ( 0 ≦ x , y ≦ l ) x,y(0≦x,y≦l)x,y(0≦x,y≦l)，意义如上所述。数据保证一定存在至少一个这样的位置。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
由于实数的计算存在误差，当误差的量级不超过10 − 6 10^{−6}10−6时，您的答案都将被接受。具体来说，设您的答案为a aa，标准答案为b bb，当且仅当∣ a − b ∣ m a x ( 1 , ∣ b ∣ ) ≤ 10 − 6 \frac{∣a−b∣}{max(1,∣b∣)}≤10^{−6}max(1,∣b∣)∣a−b∣≤10−6时，您的答案将被接受。
示例1
输入：
1 2 1 1 1输出：
0 0示例2
输入：
3 6 1 2 3 1 4 1 5 4 1输出：
2.92697 5.762122解题思路
本题核心是暴力枚举圆周外侧点+合法性校验，依托探测器数量极少的特性快速求解。题目要求在l × l l×ll×l正方形内找到不被任何圆形探测器覆盖的点，且n ≤ 10 n≤10n≤10、数据保证有解。无需复杂的几何计算，直接遍历每个探测器的圆周，生成圆周上的点并做微小偏移（确保点在圆外），再通过校验函数判断：点是否在地图范围内、是否未被所有探测器覆盖。一旦找到合法点立即输出。该方法简单直接，规避了圆相交、区域划分等复杂逻辑，枚举效率极高，完美适配题目约束。
总结
核心逻辑：利用n ≤ 10 n≤10n≤10的极小数据规模，枚举圆周边缘偏移点，快速筛选合法位置。
关键操作：圆周坐标生成、微小偏移避免落入圆内、双重合法性校验（地图边界+无覆盖）。
效率保障：无复杂算法，纯暴力枚举，运行速度极快，严格满足时间限制。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;doubledis(doublex1,doubley1,doublex2,doubley2){doubledx=abs(x1-x2),dy=abs(y1-y2);returnsqrt(dx*dx+dy*dy);}usingtddd=tuple<double,double,double>;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,l;cin>>n>>l;doubleeps=1e-6;doubledelta=1e-3;vector<tddd>a(n+1);for(ll i=1;i<=n;i++){ll x,y,r;cin>>x>>y>>r;a[i]={x,y,r};}autocheck=[&](double_x,double_y){if(_x<0||_x>l||_y<0||_y>l)returnfalse;for(auto[x,y,r]:a)if(dis(x,y,_x,_y)<=r+eps)returnfalse;returntrue;};for(ll i=1;i<=n;i++){for(ll j=1;j<=359000;j++){auto[x,y,r]=a[i];doublecur_x=x+r*cos(j/1000.0)+delta;doublecur_y=x+r*sin(j/1000.0)+delta;if(check(cur_x,cur_y)){cout<<fixed<<setprecision(10)<<cur_x<<' '<<cur_y<<endl;return0;}}}return0;}