글 읽기 - 1004 어린 왕자... 무엇이 틀렸을까요...

flute999 9년 전 0

안녕하세요?
궁리를 아무리 해보아도 제가 생각한 것 외에는 케이스가 없을 것 같은데, 계속 오답이라 답답하여 질문을 올립니다.

1. 내부 행성계를 포함하지 않는 행성계에 시작/끝이 있으면 0
2. 같은 행성계 내이나 내부 행성계에 따로 떨어져 있으면 진입/탈출 회수 만큼 카운트

이외에는 지문에 나와 있는 그대로라 딱히 예외 상황이 없을 것 같은데요,

답답하여 도움을 얻고자 질문을 드립니다.
도와주시면 감사하겠습니다.

#include <string.h>
#include <math.h>

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;




class CLePetitPrince
{
public:
	CLePetitPrince();

	void Proceed();
	
protected:
	void Input();

	void Start();

	int x1, y1;
	int x2, y2;

	
	struct SPlanet
	{
		int cx, cy;
		int r;
	};

	vector<SPlanet> planets;

	static bool PLess(SPlanet e1, SPlanet e2);
};


CLePetitPrince::CLePetitPrince()
{
}


void CLePetitPrince::Input()
{
	cin >> x1 >> y1 >> x2 >> y2;

	int num_planets;

	planets.clear();

	cin >> num_planets;
	for( ; num_planets > 0; num_planets--)
	{
		SPlanet s;
		cin >> s.cx >> s.cy >> s.r;

		planets.push_back(s);
	}
}



bool CLePetitPrince::PLess( SPlanet e1, SPlanet e2)
{
	return e1.r < e2.r;
}

void CLePetitPrince::Start()
{
	int C = 0;
	vector<SPlanet> start_planets;

	int i, j;
	for(j=0; j<planets.size(); j++)
	{
		const SPlanet& p = planets[j];

		int sx1 = abs( x1 - p.cx );
		int sy1 = abs( y1 - p.cy );

		double s_r = sqrt((double)(sx1 * sx1 + sy1 * sy1));

		if( p.r > s_r ) start_planets.push_back(p);
	}

	sort( start_planets.begin(), start_planets.end(), PLess );

	for( i=0; i<start_planets.size(); i++)
	{
		const SPlanet& p = start_planets[i];

		int sx2 = abs( x2 - p.cx );
		int sy2 = abs( y2 - p.cy );

		double e_r = sqrt((double)(sx2 * sx2 + sy2 * sy2));

		if( p.r > e_r ) break;

		C++;
	}

	for(j=0; j<planets.size(); j++)
	{
		const SPlanet& p = planets[j];

		int sx2 = abs( x2 - p.cx );
		int sy2 = abs( y2 - p.cy );

		double e_r = sqrt((double)(sx2 * sx2 + sy2 * sy2));

		if( p.r > e_r )
		{
			for(i=0; i<start_planets.size(); i++)
			{
				const SPlanet& p2 = start_planets[i];

				if( p.cx == p2.cx && p.cy == p2.cy && p.r == p.r )
				{
					break;
				}
			}
			if( i >= start_planets.size() )
				C++;
		}
	}

	cout << C << endl;
}


void CLePetitPrince::Proceed()
{
	int T;
	cin >> T;

	int i;
	for(i=0; i<T; i++)
	{
		Input();

		Start();
	}
}


int main()
{
	CLePetitPrince o;

	o.Proceed();

	return 0;
}

Nada 9년 전 0

아래 질문의 원인과 마찬가지로 double형의 오차 때문에 오답이겠네요.

baekjoon 9년 전 0

문제를 풀 때 되도록 소수점(float, double)을 사용하지 않는 것이 좋습니다.

이 문제는 double을 사용하지 않고 풀 수 있습니다.

flute999 9년 전 0

답변 감사합니다. 그런데 int형으로 casting을 해도 안되는 것을 보니 무언가 잘못된 접근을 한 것 같네요. double을 아예 안쓰는 방향으로 다시 접근해 보겠습니다.

flute999 9년 전 0

아래처럼 sqrt를 하나 만들어서 사용해도 안되네요. 혹시 추가적으로 힌트가 없을까요? 제가 생각하지 못한 조건이 있는 것인지...

int CLePetitPrince::my_sqrt( int x )
{
	int r;
	for(r=0; ; r++)
	{
		int r2 = r * r;
		if( r2 == x ) return r;
		if( r2 > x ) return r-1;
	}
}

WeissBlume 9년 전 0

sqrt를 사용하기보다는 아예 모든 것을 제곱해서 생각해보세요..

flute999 9년 전 1

답변 주신 분들 정말 감사 드립니다. 덕분에 답을 맞히게 되었습니다.

사실 sqrt 자체가 직접적인 원인은 아니었지만, sqrt를 걷어낸 덕분에 문제를 isolation 할 수 있었습니다.

어제 하루 종일 업무도 못하고 이 거에 매달렸고, 오늘도 그럴 뻔 했는데, 정말 감사 드려요. ^-^

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

문제

문제

출처

ICPC

1004 어린 왕자... 무엇이 틀렸을까요...

flute999 9년 전 0

Nada 9년 전 0

baekjoon 9년 전 0

flute999 9년 전 0

flute999 9년 전 0

WeissBlume 9년 전 0

flute999 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말