글 읽기 - 제발 반례나 코드 오류좀 알려주세요 ㅜㅜ 3시간째 고민하고 있습니다.

dmz2080 4년 전 0

구글링해도 잘 나오지 않네요 ㅜㅜ

삼분탐색으로 풀어서 정답을 찾은거 같은데 계속 틀리다고 하네요..

예제 문제들은 오차 10^-6 까지 모두 잘 맞습니다. 그 이상의 정확도(10^-7 이하부터)는 조금 차이가 있습니다.

도대체 뭐가 문제인지 모르겠습니다.

혹시 문법 문제일 수도 있는데 (제가 C++ 초보라서요 ;;) 답변 부탁드립니다. !!

감사합니다.

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

const int inx = 1000000; //인덱스 길이

double a1[2], b1[2], a2[2], b2[2], a3[2], b3[2], a4[2], b4[2];//각 포인터들

double d1, d2, d3, d4;//삼분탐색에 사용될 길이들
int i1, i2, i3,i4; // 인덱스 종류

double dist(double *x, double *y) {
	return	pow(pow(x[0] - y[0], 2) + pow(x[1] - y[1], 2),0.5);
}

int main() {

	double A[3][3];
	double B[3][3];

	for (int x = 1; x <= 2; x++) {
		for (int y = 1; y <= 2; y++) {
			cin >> A[x][y];//A Node
		}
	}
	for (int x = 1; x <= 2; x++) {
		for (int y = 1; y <= 2; y++) {
			cin >> B[x][y];//B node
		}
	}

	a1[0] = A[1][1];
	a1[1] = A[1][2];
	b1[0] = B[1][1];
	b1[1] = B[1][2];
	d1= dist(a1, b1);
	
	a4[0] = A[2][1];
	a4[1] = A[2][2];
	b4[0] = B[2][1];
	b4[1] = B[2][2];
	d4 = dist(a4, b4);

	i1 = 0;
	i4 = inx;

	while (i4>=i1) {

		i2 = i1+(i4 - i1) / 3;
		i3 = i1+2*(i4 - i1) / 3;

		
		a2[0] = a1[0] + (a4[0] - a1[0]) * i2 / inx;
		a2[1] = a1[1] + (a4[1] - a1[1]) * i2 / inx;
		b2[0] = b1[0] + (b4[0] - b1[0]) * i2 / inx;
		b2[1] = b1[1] + (b4[1] - b1[1]) * i2 / inx;

		d2 = dist(a2, b2);

		a3[0] = a1[0] + (a4[0] - a1[0]) * i3 / inx;
		a3[1] = a1[1] + (a4[1] - a1[1]) * i3 / inx;
		b3[0] = b1[0] + (b4[0] - b1[0]) * i3 / inx;
		b3[1] = b1[1] + (b4[1] - b1[1]) * i3 / inx;

		d3 = dist(a3, b3);


		if (d3 >= d2) {
			i4 = i3 - 1;
		}
		else {
			i1 = i2 + 1; 
		}
		
	}
	cout << std::setprecision(10);
	cout << d2;
	
	return 0;
}

sait2000 4년 전 0

오차가 너무 큽니다. 아래 케이스의 답은 정확히 1입니다. 지금 제 쪽에서 돌려서 나오는 답은 1.009999네요.

in:
0 0 5000 10000 10000 0 5001 10000

out:
1

sait2000 4년 전 1

삼분탐색에 사용하는 인덱스를 정수형 말고 실수형을 써보세요

dmz2080 4년 전 0

감사합니다.

조언해주신데로 인덱스를 실수형으로 바꾸고

인덱스 레인지를 100000000000 로 하니까 해결되네요.

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

문제

문제

출처

ICPC

제발 반례나 코드 오류좀 알려주세요 ㅜㅜ 3시간째 고민하고 있습니다.

dmz2080 4년 전 0

sait2000 4년 전 0

sait2000 4년 전 1

dmz2080 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말