class circleInfo{
int x, y, r;
}
class TreeNode{
TreeNode parent=null;
circleInfo data=new circleInfo();
ArrayList child=new ArrayList();
}
public class Main {
static int longest=0;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int TestCase=Integer.parseInt(br.readLine());
for(int tc=0;tc<TestCase;tc++) {
int N=Integer.parseInt(br.readLine());
TreeNode[] nodeArr=new TreeNode[N];
for(int i=0;i<N;i++) {
nodeArr[i]=new TreeNode();
StringTokenizer st=new StringTokenizer(br.readLine());
nodeArr[i].data.x=Integer.parseInt(st.nextToken());
nodeArr[i].data.y=Integer.parseInt(st.nextToken());
nodeArr[i].data.r=Integer.parseInt(st.nextToken());
}
TreeNode root=nodeArr[0];
//성벽에 포함관계에 알맞게끔 노드를 트리에 삽입
for(int i=1;i<nodeArr.length;i++)
addNode(root,nodeArr[i]);
longest=longestLeaf2LeafDistance(root);
LongestDistance(root);
int result=Math.max(longest, treeHeight(root));
System.out.println(result);
longest=0;
}
}
//root트리의 서브트리에서 leaf-루트-leaf의 최대 경로 반환
static void LongestDistance(TreeNode root) {
if(root.child.size()==0) return;
for(int i=0;i<root.child.size();i++) {
longest=Math.max(longest, longestLeaf2LeafDistance(root.child.get(i)));
LongestDistance(root.child.get(i));
}
}
//n을 root로 했을때 leaf-root-leaf간 최대거리
static int longestLeaf2LeafDistance(TreeNode n) {
int max1=0,max2=0;
if(n.child.size()<2) return 0;
for(int i=0;i<n.child.size();i++) {
int treeH=treeHeight(n.child.get(i));
if(max1<treeH) {
max2=max1;
max1=treeH;
}else if(max1>=treeH && max2<treeH) {
max2=treeH;
}
}
return max1+max2+2;
}
//트리의 높이반환 O(n)
static int treeHeight(TreeNode n) {
if(n.child.size()==0) return 0;
int maxH=0;
for(int i=0;i<n.child.size();i++) {
int childH=treeHeight(n.child.get(i));
if(maxH<childH)
maxH=childH;
}
return maxH+1;
}
//포함관계에 알맞게끔 트리에 노드를 추가
static void addNode(TreeNode root, TreeNode elem) {
int flagIsChild=isChild(root, elem);
if(flagIsChild==1) {
//root가 elem을 포함하는 경우, root의 자식과의 포함관계를 탐색
for(int i=0;i<root.child.size();i++) {
int fc=isChild(root.child.get(i),elem);
if(fc==1) { //만약 root.child[i]가 elem을 포함한다면 child를 root로 해서 재귀호출
addNode(root.child.get(i),elem);
return;
}else if(fc==-1) { //만약 elem이 root.child[i]를 포함한다면, 그 사이에 삽입
root.child.get(i).parent=elem;
elem.parent=root;
return;
}
}
root.child.add(elem);
}else if(flagIsChild==-1) {
//elem이 root를 포함, root와 root의 부모사이에 elem을 삽입
elem.parent=root.parent;
root.parent=elem;
}else {
// 포함관계가 아닌 경우, 형제로 만들어 줌
root.parent.child.add(elem);
}
}
//두 노드간 포함관계를 반환
static int isChild(TreeNode root, TreeNode elem) {
double rootRadius=root.data.r;
double elemRadius=elem.data.r;
double d=Math.sqrt(Math.pow(root.data.x-elem.data.x, 2)+Math.pow(root.data.y-elem.data.y, 2));
if(rootRadius>elemRadius && d<rootRadius-elemRadius)//root가 elem을 포함하는 경우, 1반환
return 1;
else if(rootRadius<elemRadius && d<elemRadius-rootRadius)//elem이 root를 포함, -1반환
return -1;
return 0; //둘 관계가 서로 포함관계가 아니면 0반환
}
}
}
~~~
8년 전
0개의 댓글이 있습니다.
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면
온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야
합니다. 현재 문제를 푸셨습니다.
mook1993@naver.com
책에 있는 아이디어 참고해서 제 나름 대로 한다고 했는데 제출하면 자꾸 오답처리 되네요...
제 소스코드에서 어떤게 문제점이 될 수 있는지 찾아주시면 감사하겠습니다~!!!
문제 URL
FORTRESS: 요새
고려한 사항들
~~~ JAVA
package FORTRESS;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
class circleInfo{ child=new ArrayList();
int x, y, r;
}
class TreeNode{
TreeNode parent=null;
circleInfo data=new circleInfo();
ArrayList
}
public class Main {
static int longest=0;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int TestCase=Integer.parseInt(br.readLine());
}
}
~~~
8년 전