import java.util.StringTokenizer;
import java.util.Scanner;
class Solution {
static StringTokenizer st;
static String[] result;
static Country[] countries;
public static void main(String[] args) throws Exception{
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int T;
T=Integer.parseInt(sc.nextLine());
StringBuffer sb = new StringBuffer();
for(int test_case = 1; test_case <= T; test_case++)
{
int N = Integer.parseInt(sc.nextLine());
countries = new Country[N+1];
for(int i=1; i<=N; i++) {
st = new StringTokenizer(sc.nextLine()," ");
int X = Integer.parseInt(st.nextToken());
int Y = Integer.parseInt(st.nextToken());
double S = Double.parseDouble(st.nextToken());
countries[i]=new Country(X,Y,S);
}
result = new String[N+1];
for(int i=1; i<=N; i++) {
double maxThreat =0;
for(int j=1; j<=N; j++) {
if(i==j)continue;
double threat = threat(countries[j],countries[i]);
if(threat>countries[i].s) {
if(threat>maxThreat) {
maxThreat = threat;
countries[i].control=j;
}else if(threat==maxThreat) {
countries[i].control=-1;
}
}
}
}
sb.append("#"+test_case+" ");
String result ="";
for(int i=1; i<=N; i++) {
result+= getResult(i)+" ";
}
sb.append(result+'\n');
}
System.out.print(sb);
}
static double threat(Country i, Country j) {
return i.s/(Math.pow((j.x-i.x),2)+Math.pow((j.y-i.y),2));
}
static String getResult(int i) {
if(countries[i].control==-1) { //여러개
return "D";
}else if(countries[i].control==0) {
return "K";
}else{
return Integer.toString(getAncestor(i));
}
}
static int getAncestor(int i) {
if(countries[i].control == -1 || countries[i].control== 0) {
return i;
}else {
return getAncestor(countries[i].control);
}
}
}
class Country{
int x;
int y;
double s; //군사력
int control=0;
public Country(int x, int y, double s) {
this.x = x;
this.y = y;
this.s = s;
}
}
자꾸 테케 일부만 맞아가지고
화만 가득이다가 풀이 봤다..
(근데 난,,문제 안풀리면 웰케 화가 날까 ,,,? ㅋ ㅎ ㅋ ㅎ 🤯😂)
내가 못 풀 문제였던 것 같다. 잘 안풀어본 문제..
문제의 부분은 정답 출력과 getAncestor 부분..
만약 3을 5가 지배했다면 3이 지배했던 나라들도 5가 지배하는 걸로 바뀌게 되는데
이 부분 구현을 잘못했다.
i를 누가 지배를 하고 있다면, i를 지배한 나라의 지배한 나라를 확인 ........ 이런 식으로 타고타고,,
그래서 ancestor..
이렇게 푸는 방식을 전혀 생각하지 못한 부분이었다.😭