글 읽기 - 1004번 트리로..

sjkim2322 7년 전 0

트리로 해볼려하는데 왜자꾸틀릴까여..

#include<stdio.h>
#include<stdlib.h>
int T;
int n;
typedef struct node
{
	int x;
	int y;
	int r;
	int childcnt;
	struct node *parent;
	struct node *next[51];
}node;
node root;
int ischild(node* start,node * tmp)
{
	if(((start->x)-(tmp->x)) * ((start->x)-(tmp->x)) +((start->y)-(tmp->y)) * ((start->y)-(tmp->y)) > (start->r+tmp->r)  * (start->r+tmp->r))
	{
		return 0;
	}
	else
	{
        if(start->r > tmp->r)
		    return 1;
        else
            return 0;
	}
}
int insert(node* start,node * tmp)
{

	int i;
	node * mytmp;
	if(ischild(start,tmp))
	{
		for(i=0;i<start->childcnt;i++)
		{
			if(insert(start->next[i],tmp))
				return 1;
			else
				if(ischild(tmp,start->next[i]))
				{
					mytmp=start->next[i];
					tmp->parent=start;
					mytmp->parent=tmp;
					start->next[i]=tmp;
					tmp->next[tmp->childcnt++]=mytmp;
					return 1;
				}
        }
		tmp->parent=start;
		start->next[start->childcnt++]=tmp;
		return 1;
	}
	else
		return 0;

}
int finddown(node * start, node * end, int cnt)
{
	int i;
	for(i=0;i<start->childcnt;i++)
	{
		if(ischild(start->next[i],end))
			return finddown(start->next[i],end,cnt+1);
		else if(start->next[i]==end)
			return cnt;
			
	}
}
int find(node * start , node * end,int cnt)
{
	if(ischild(start,end))
		return cnt + finddown(start,end,0);
	else
		return 	find(start->parent,end,cnt+1);
}
int main()
{
	int x1,y1,x2,y2;
	int i,j;
	int t;
	node * tmp;
	scanf("%d",&T);
	for(j=0;j<T;j++)
	{
	scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
	scanf("%d", &n);
	root.x=0;
	root.y=0;
	root.r=4000;
	root.childcnt=0;
	for(i=0;i<n;i++)
	{	
		tmp = (node *) malloc(sizeof(node));
		tmp->childcnt=0;
		scanf("%d %d %d",&(tmp->x),&(tmp->y),&(tmp->r));
		insert(&root,tmp);
		//printf("P x :%d y :%d\n",tmp->parent->x,tmp->parent->y);
	}

	node * start = (node *)malloc(sizeof(node));
	start->x=x1;start->y=y1;start->r=0;
	node * end = (node *) malloc(sizeof(node));
	end->x =x2;end->y=y2;end->r=0;
	insert(&root,start);
	//printf("%d %d",start->parent->x,start->parent->y);
	insert(&root,end);
	//printf("%d %d",end->parent->x,end->parent->y);
	printf("%d\n",find(start, end,0)-1);
	}

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1004번 트리로..

sjkim2322 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말