FORTRESS

AOJ FORTRESS

SOL)

1.반지름이 큰 원부터 순서대로 트리를 구성한다.
2.만약 root속에 val이 속할 수 있다면 root의 자식들에게도 val이 속할수 있는지
  검사한다. 속할수 있다면 재귀적함수를 함수를 호출한다.
3.결국 해당 자식들에게 속할 수 없을때가 나오는데 이때에 val을 자식으로 추가
4.트리를 구성하면서 깊이 값 dept를 넣어줌
5.leaf와 leaf사이의 최대거리는 leaf[i].dept + leaf[j].dept - 2*parent.dept이다.
 (여기서 parent는 leaf[i]와 leaf[j]를 공통으로 포함하는 최초의 부모노드)
 (만약 leaf가 한개라면 답은 leaf.dept)

[-] Collapse

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

struct Strawgoh{
    Strawgoh() : parent(NULL){};
    int x, y;
    int r;
    int dept;
    Strawgoh* parent;
    vector<Strawgoh*> child;
};
vector<Strawgoh> info;
vector<Strawgoh*> leaf;

int distance(int x1, int y1, int x2, int y2){
    return (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
}

bool comp(const Strawgoh& l, const Strawgoh& r){
    return l.r > r.r;
}

bool makeTree(Strawgoh *root, Strawgoh *val, int dept){
    bool check = false;
    if (distance(root->x, root->y, val->x, val->y) < root->r * root->r){
        for (int i = 0; i < root->child.size(); i++){
            check = makeTree(root->child[i], val, dept + 1);
            if (check) break;
        }
        if (!check) {
            root->child.push_back(val);
            val->parent = root;
            val->dept = dept;
            check = true;
        }
    }
    return check;
}
int findMaxHeight(){
    int ans = 0;
    if (leaf.size() == 1) return leaf[0]->dept;

    for (int i = 0; i < leaf.size(); i++){
        for (int j = i + 1; j < leaf.size(); j++){
            Strawgoh* p = leaf[i]->parent;

            while (true){
                if (distance(p->x, p->y, leaf[j]->x, leaf[j]->y) < (p->r * p->r))
                    break;
                p = p->parent;
            }
            ans = max(ans, leaf[i]->dept + leaf[j]->dept - 2 * p->dept);
        }
    }
    return ans;
}

int main(){
    int t; scanf("%d", &t);
    while (t--){
        leaf.clear();
        int n; scanf("%d", &n);
        info = vector<Strawgoh>(n);
        for (int i = 0; i < n; i++)
            scanf("%d%d%d", &info[i].x, &info[i].y, &info[i].r);

        info[0].parent = &info[0];
        info[0].dept = 0;

        sort(info.begin(), info.end(), comp);

        for (int i = 1; i < n; i++)
            makeTree(&info[0], &info[i], 1);

        for (int i = 0; i < n; i++){
            if (info[i].child.size() == 0)
                leaf.push_back(&info[i]);
        }

        printf("%d\n", findMaxHeight());
    }
}