|
:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
08/07/25 22:17
수학적으로는 두점 사이가 제일 가까운 좌표 2개를 찾으면 되는 문제 같습니다. 저라면 별 생각없이 두점 사이 거리를 구하는 함수를 하나 만들고 순차적으로 모든 두점의 거리를 비교해 보겠습니다.
08/07/25 22:19
입력받은 좌표를 차례대로 일단 루프로 넣고(루프1), 루프 안에서 타겟이 된 좌표를 제외한 나머지 좌표들을 또 차례대로 루프로 넣어서(루프2) 그 두 타겟이 된 좌표를 피타고라스 정리로 거리를 구하면 되겠네요. 루프2에서는 각각의 좌표간 거리 중 가장 큰 값(변수1)을 도출시키고, 루프1에서는 각각의 변수1을 비교하여 가장 작은 변수1을 출력시키면 될겁니다. 변수1이 반지름이 되겠네요.
08/07/25 22:22
가장 무식한 방법이 가장 단순한 방법입니다.
일단 구조체 배열 정도이 필요하겠습니다. i는 index x, y 그리고 계산해야 할 인덱스 변수 하나 더 필요합니다. min은 최소값이 되는 인덱스 좌표의 인덱스 번호 min_val은 그 최소값입니다. i x y min min_val 0 a b 1 c d 2 e f . . . . . . n y z 이런식으로 저장해 주면 되고 for(index가 n이 될때까지) for(변수 i <=index+1){ // 인덱스 0번은 1번부터 n번까지 인덱스 1번은 2번부터 n번까지 왜냐면 인덱스 1번과 0번은 0번대에서 해결 .... } ....부분이 코딩 부분입니다. 수학적 아이디어를 쓰자면 좌표 x,y에서 1번 인덱스의 x,y까지 거리를 비교합니다. 그것이 원의 반지름이 됩니다. (x1-x2)²+(y1-y2)²의 양의 루트값이죠. 이것은 math.h에 있는 함수로 해결할 수 있습니다. sqrt였던가...? 잘 기억 안나니 책 찾아서 참고해 주시고요. 0~n까지 돌아가며 최소값이 되는 인덱스와 최소값을 찾는 작업 한번 해주시면 대충 될겁니다. 이상입니다. 시간복잡도는 n²/2입니다.
08/07/25 22:29
무식한 방법으로...
각 좌표값이 A1(x1, y1), A2(x2,y2), A3(x3,y3).....라고 가정하고.... 입력 값이 (x1, y1), (x2, y2), (x3,y3)...(xn, yn)식으로 값을 받는다고 가정하면... for(i=1;i<=n;i++) for(j=1;j<=n;j++){ temp[i][j] = ((x[i]-x[j])^2 + (y[i]-y[j])^2); } 이렇게 각 좌표간의 반지름 값을 전부 계산한뒤에... for(i=1;i<=n;i++) for(j=1;j<=n;j++){ if(temp[i][j] < temp[i+1][j+1]){ min = temp[i][j]; else{ min = temp[i+1][j+1]; 각 배열에 있는 값중에 0이 아닌(0 이면 원이 아니죠) 최소값을 찾아내면.. 그게 정답이 아닌지요??? C 코딩을 손 놓은지가...어언 4년이 넘어서...ㅡㅡ;; 그냥 간략히 정리만 해봤는데...뒤에 고수분께 패스....*^^*
08/07/25 22:47
정확히 '원 위에' 있어야 포함인지, 아니면 '원 안에' 있어도 포함으로 인정하는지에 따라 다를 것 같습니다.
뭐 설명은 윗분들이 해주셨으니 넘어가고, 한 가지 팁은 Sqrt를 씌워 굳이 거리로 비교할 것이 아니라, 그냥 거리^2을 가지고 비교하는 것이 더 낫습니다. 특히 입력되는 좌표가 정수라면 더더욱 말이죠. Int가 아닌 Double에서는 연산 회수를 최소화해야 오차를 줄일 수 있습니다.
08/07/25 22:50
다른분들 답주신게 조금씩 이상한게 있는것 같은데;;;;
제가 생각하는 답은 이렇습니다. 1. 주어진 N개의 좌표를 가지고 중심점 C 를 구한다. 2. 주어진 N개의 좌표중 중심점 C와 가장 가까운 좌표 (Cx, Cy)를 구한다. 3. 주어진 N개의 좌표중 (Cx, Cy)와 가장 먼 좌표 (Rx, Ry)를 구한다. 4. (Cx, Cy)와 (Rx, Ry)사이의 거리를 구한다. 2번에서 중심점 구하고, 4번에서 원의 반지름이 나옵니다.
08/07/25 22:59
음.. N이 매우 크다면 Convex Hull을 우선 그려놓고, N개의 점들에 대해 Convex Hull 위에 있는 점들과의 거리만 계산하면 될 것 같습니다. 시간복잡도는 N * (Convex Hull 위의 정점 수) 이고 Convex Hull 위의 정점 수는 제 기억엔 평균적으로 lg N정도였던것으로..
08/07/25 23:06
꿀호떡a님// 입력받은 좌표들의 평균점(산술평균)을 의미하는 것일겁니다. 그 평균점과 입력받은 좌표간 거리를 비교하여 가장 가까운 좌표가 중심점이 되겠죠. 연산처리도 빨라질테고요.
08/07/25 23:10
#include "stdafx.h"
#include <stdlib.h> #include <math.h> #include <float.h> struct Point float x; float y; const int num_points = 4; Point points[num_points] = {10, 10 20, 20 , 30, 30 , 40, 40
}; int _tmain(int argc, _TCHAR* argv[]) float xSum = 0; float ySum = 0; int i; for ( i = 0; i < num_points; ++i ) { xSum += points[i].x; ySum += points[i].y; float cX = xSum / num_points; float cY = ySum / num_points; float dist; float distMin = FLT_MAX; int indexMin = -1; for ( i = 0; i < num_points; ++i ) dist = (points[i].x - cX) * (points[i].x - cX) + (points[i].y - cY ) * (points[i].y - cY ); if ( dist <= distMin ) { indexMin = i; distMin = dist; } if ( indexMin == -1 ) exit( -1 ); cX = points[indexMin].x; cY = points[indexMin].y; float distMax = 0; int indexMax = -1; for ( i = 0; i < num_points; ++i ) dist = (points[i].x - cX) * (points[i].x - cX) + (points[i].y - cY ) * (points[i].y - cY ); if ( dist >= distMax ) { indexMax = i; distMax = dist; } if ( indexMax == -1 ) exit( -1 ); float rX = points[indexMax].x; float rY = points[indexMax].y; dist = sqrt( (rX - cX) * (rX - cX) + (rY - cY) * (rY - cY) ); printf( " Center : (%f, %f), Radius = %f\n", cX, cY, dist ); return 0; } 대충 짜봤습니다. 컴파일 에러는 안나는것만 확인하고 테스트로 넣은 값에서는 정상 동작은 확인했습니다.
08/07/25 23:21
문제는 확실한것 같습니다.
내포함이라고 하였으니 원의 내부 또는 포함입니다. 모든 점을 원 안에 들이거나 원 상에 놓이게 할 수 있는 최소 반지름과 중심점을 구하는 문제이겠네요.
08/07/25 23:23
NULL POINTER님 증명 가능하십니까?
중심점을 산술평균이라고 했을때 그게 성립하지 않는 경우가 있습니다. (0,0) 부근에 점들이 10만개쯤 몰려있고, (5,0)에 한개, (10,0)에 한 개 있으면, 중심점은 5,0이 되어야 하지만, 제시하신 알고리즘은 0,0 부근의 점을 선택합니다.
08/07/25 23:26
제가 생각하는 방법은 꿀호떡a님이 제시해주신 방법과 같구요, 아마 맞는것 같습니다.
Convex Hull 내부의 점에서 가장 거리가 먼 점은 반드시 Convex Hull 위에 있게 됩니다. 이 성질을 잘 이용하면, Rotating Calipers 방법을 이용하여 O ( N log N ) 시간내에 답을 구할 수 있을 지도 모르겠습니다만, 여기까지는 안 해봤고 될지도 모르겠습니다....
08/07/25 23:26
물론 그냥 C언어를 익히기 위한 과제였다면 O(N^2)의 Naive한 알고리즘으로도 충분할 것 같습니다.
가장 간단한 방법은 모든 점에 대해서 각각 중심점이라고 가정한 뒤, 이 때 필요한 원의 반지름의 크기(O(N)의 루프를 돌면서 각각의 점과 가정한 중심점과의 거리의 최대값)를 비교해서 최소를 찾아주면 되겠습니다.
08/07/25 23:31
n이 작다면,
각 점을 중점으로 가정해서 나머지 점과의 거리중 가장 큰 것이 반지름입니다. 모든 점을 중점으로 가정해서 가장 작은 반지름이 나온 점이 중점이고 그 점에서 가장 먼거리가 반지름이 됩니다. n이 크다면, Convex Hull로 울타리에 위치하는 점들을 골라내고 n개의 점을 중점으로 가정해서 울타리 점들과의 거리를 계산합니다. 방법은 위와 비슷하지만 불필요한 연산이 제거 됩니다. 정점중에 하나가 중심이 되는 것으로 봐서 상단의 방법으로 풀이하라는 의도 같습니다. 하단의 방법(Convex Hull)을 의도했다면 정점 중심 조건도 빼버렸을 것같네요. n의 범위를 제시하지 않은걸로 봐서 그냥 학부 코딩연습 과제인듯 합니다. 시간복잡도는 고려하지 말고 편한방법(상단)으로 푸세요.
08/07/26 00:10
아, 문제를 확실히 하자면
원안에 좌표가 포함해야 되고 원의 선상에 포함하는 부분까지라는 의미입니다. n은 0~100까지 였는데 수학적으로 어떻게 해야되는지가 궁금해서 적진 않았습니다. 원래 문제는 이거였습니다. - n개의 좌표(실수 x, y)가 입력되어 있다. 이 파일의 이름은 c드라이브에 input.txt라고 하자. 이 파일의 좌표를, 구조체를 동적할당으로 생성하여 입력 처리하고, 이 점들을 내포함하는 반지름이 가장 작은 원을 찾아본다. 여기서 원의 중심점은 입력되는 점들 가운데 하나이어야 하고, 포함한다는 의미는 원의 선상에 존재하는 점도 해당된다. 이 결과는 c드라이브에 학번.txt 파일에 출력하도록 한다. 좌표는 0~100사이의 실수로 입력되고, 점의 개수는 최대 100개로 한정한다. 아직 댓글들을 다 못읽어 봤지만 다시한번 감사의 말씀 드리겠습니다. ^^
08/07/26 00:15
아 참고로 n이 100개정도면 Memex님이 언급하신 n이 작은 경우에 해당됩니다. 이런 문제의 경우엔 10000개이상이면 좀 크다고 할 수 있습니다.
|
||||||||||