글 읽기 - 1007번 틀렸습니다

yousrain 4년 전 0

엄청 단순하게 구현해서 알고리즘 자체는 오류가 없어보입니다만,

계속 틀렸습니다가 나옵니다 ㅠㅠ

왜 틀리는 걸까요?? 예외적인 상황이 나올 수 있나요?? ㅠㅠ

알고리즘은 간단합니다

- 모든 점에 대해 거리를 구하므로 4중 for루프를 돌린다

- 이미 선택한 점 continue로 넘긴다

- N==2인 경우만 4중 루프를 돌 수 없으므로

따로 처리해준다.

확인 한번만 부탁드립니다 ㅠㅠ

#include<stdio.h>
#include<cmath>
class pos{
    public:
	long long x = 0, y = 0;
};
int T;
int N;
pos map[20];
double result[10000];
double dis(pos);
double min(double a, double b) { return a < b ? a : b;}

int main(){
    scanf("%d", &T);
    for(int i = 0; i < T; i++) result[i] = -1;
    for(int i = 0; i < T; i++){
	scanf("%d", &N);
	for(int j = 0; j < N; j++){
	    scanf("%d %d", &map[j].x, &map[j].y);
	}
	if(N == 2){
	    pos r = {map[0].x - map[1].x, map[0].y - map[1].y};
	    result[i] = dis(r);
	    continue;
	}

	for(int j = 0; j < N; j++){
	    for(int k = 0; k < N; k++){
		if(k == j) continue;
		pos s = {map[j].x - map[k].x, map[j].y - map[k].y};
		for(int m = 0; m < N; m++){
		    if(m == j || m == k) continue;
		    for(int n = 0; n < N; n++){
			if(n == j || n == k || n == m) continue;
			pos e = {map[m].x - map[n].x, map[m].y - map[n].y};
			pos r = {s.x + e.x, s.y + e.y};
			if(result[i] == -1) result[i] = dis(r);
			else result[i] = min(result[i], dis(r));
		    }
		}
	    }
	}
    }
    for(int i = 0; i < T; i++) printf("%.6f\n", result[i]);
    return 0;
}

double dis(pos a){
    long res = a.x * a.x + a.y * a.y;
    return sqrt((double)res);
}

1207koo 4년 전 1

제가 이해한 것이 맞다면 문제를 잘못 이해하신 것 같습니다.

이 문제는 모든 점을 한 번씩 써서 n/2개의 벡터를 만들고 그의 합인 벡터의 길이가 최소가 되어야 합니다.

근데 이 코드는 n=2일 때 한 개의 벡터, 그 외의 경우에는 두 개만 더하는 것 같습니다...아마도...?

yousrain 4년 전 1

아아 이해했습니다 감사합니다 ㅠㅠ

말씀하신 대로 제 코드는 주어진 좌표로 만들 수 있는

모든 벡터중 두개를 골라 그 합이 가장 적은 값을 구하는 코드입니다. 그런 의도로 구현했고요...

빠르게 알려주셔서 감사합니다. 혼자 봤으면 절대 몰랐을 것 같습니다!!

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

문제

문제

출처

ICPC

1007번 틀렸습니다

yousrain 4년 전 0

1207koo 4년 전 1

yousrain 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말