C는 일련의 원입니다. 각각은 트리플 (xyr)로 표현됩니다. n 개의 주어진 집합 C가 임의의 원이 교차 하는지를 결정하는 알고리즘.

Question

C를 삼중 항 (x; y; r)으로 표현되는 원 집합이라하자. y는 이고 중심은 r입니다. 어떤 문자가 교차 하는지를 결정하기 위해 n 개의 문자 집합이 주어진개의 원을 가진 알고리즘을 설계하고 분석합니다. 1. 완전한 의사 코드 2. 입력 및 입력 크기 식별, n 3. 기본 조작 식별 4. 입력 크기에 대해 기본 조작이 수행 된 횟수 n을 계산하십시오. 5. Big-O 점근 제공 알고리즘의 복잡성에 대한 특성 분석.

두 개의 원이 교차하는 위치를 찾는 방법을 시도하고 발견했습니다. 그리고 선이 원과 교차하는 곳에서 발견되었지만 n 개의 원에 대한 알고리즘을 생각해 내는데 어려움을 겪고 있습니다.

Answer 1

N 개의 원이 교차한다고 알려주는 수식을 찾을 필요는 없습니다. 2 개의 원이 교차하는지 확인하기 위해 찾은 원을 사용하고 모든 원에 사용하십시오. 여기에 기본 의사 코드 (100 % 의사 코드 준수 여부는 확실하지 않습니다.)).

boolean findItersections(Collection C){ 
    for (circleA in C) { 
     C.remove(circleA); 
     for (circleB in C){ 
      if (isItersection(circleA, circleB)) 
       return true; 

     } 
    } 
} 

//elementary operation 

boolean isItersection(Circle a, Circle b){ 

    //distance between centers 
    float d = sqrt((a.x -b.x)^2 + (a.y-b.y)^2)); 

    if(d> a.r+b.r) 
     return false; 
    else 
     return true; 
}