algorithm dermuba triangle - andstudy/forge GitHub Wiki

CynicJJ

!ModuleMain.vb

    Public Module ModuleMain
    
    	Sub Main()
    		While True
    			Console.WriteLine(Run(Console.ReadLine()))
    		End While
    	End Sub
    
    	Function Run(ByVal input As String) As String
    		Dim strs() As String = input.Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries)
    		If strs.Length < 2 Then Return Nothing
    
    		Dim number1 As Integer = Integer.Parse(strs(0))
    		Dim number2 As Integer = Integer.Parse(strs(1))
    
    		Return Triangle.GetDistance(number1, number2).ToString()
    	End Function
    
    End Module

Triangle.vb

    Public Enum Direction
    	Up
    	Down
    End Enum
    
    Public Class Triangle
    
    	Shared Function GetDistance(ByVal number1 As Integer, ByVal number2 As Integer) As Double
    		Dim bigger As Integer = Math.Max(number1, number2)
    		Dim smaller As Integer = Math.Min(number1, number2)
    
    		Dim horizontalDistance As Double = GetHorizontalDistance(smaller, bigger)
    		Dim verticalDistance As Double = GetVerticalDistance(smaller, bigger)
    
    		Dim distance As Double = Math.Sqrt(Math.Pow(horizontalDistance, 2) + Math.Pow(verticalDistance, 2))
    		Return Math.Round(distance, 3)
    	End Function
    
    	Private Shared Function GetHorizontalDistance(ByVal number1 As Integer, ByVal number2 As Integer)
    		Dim columnDiff As Integer = GetColumn(number1) - GetColumn(number2)
    		Return columnDiff * 0.5
    	End Function
    
    	Private Shared Function GetVerticalDistance(ByVal number1 As Integer, ByVal number2 As Integer)
    		Dim rowDiff As Integer = Math.Abs(GetRow(number1) - GetRow(number2))
    		Return GetBottomDistance(number1) + (rowDiff - 1) * GetHeight() + GetTopDistance(number2)
    	End Function
    
    	Shared Function GetRow(ByVal number As Integer) As Integer
    		Dim row As Integer = 0
    
    		Dim rowFirst As Long = 0
    		While True
    			row += 1
    			rowFirst = rowFirst + GetCount(row)
    			If rowFirst > number Then Exit While
    		End While
    
    		Return row
    	End Function
    
    	Shared Function GetColumn(ByVal number As Integer) As Integer
    		Dim column As Integer
    
    		Dim rowFirst As Long
    		For row As Integer = 1 To GetRow(number) - 1
    			rowFirst = rowFirst + GetCount(row)
    		Next
    
    		Dim rowLast As Long = rowFirst + GetCount(GetRow(number)) - 1
    		Dim rowMiddle As Long = (rowFirst + rowLast) \ 2
    
    		column = number - rowMiddle
    		Return column
    	End Function
    
    	Private Shared Function GetDirection(ByVal number As Integer) As Direction
    		If GetRow(number) And 1 Then
    			If GetColumn(number) And 1 Then
    				Return Direction.Down
    			Else
    				Return Direction.Up
    			End If
    		Else
    			If GetColumn(number) And 1 Then
    				Return Direction.Up
    			Else
    				Return Direction.Down
    			End If
    		End If
    	End Function
    
    	Private Shared Function GetTopDistance(ByVal number As Integer) As Double
    		If GetDirection(number) = Direction.Up Then
    			Return (GetHeight() - GetCenterDistance())
    		Else
    			Return GetCenterDistance()
    		End If
    	End Function
    
    	Private Shared Function GetBottomDistance(ByVal number As Integer) As Double
    		If GetDirection(number) = Direction.Up Then
    			Return GetCenterDistance()
    		Else
    			Return (GetHeight() - GetCenterDistance())
    		End If
    	End Function
    
    	Shared Function GetHeight() As Double
    		Return (Math.Sqrt(3) / 2)
    	End Function
    
    	Shared Function GetCenterDistance() As Double
    		Return (1 / Math.Sqrt(3) / 2)
    	End Function
    
    	Private Shared Function GetCount(ByVal row As Integer) As Integer
    		Return ((row - 1) * 2) + 1
    	End Function
    
    End Class

!TriangleTest.vb

    <TestClass()> _
    Public Class TriangleTest
    
    	<TestMethod()> _
    	Public Sub GetRowTest()
    		Assert.AreEqual(1, Triangle.GetRow(0))
    		Assert.AreEqual(2, Triangle.GetRow(1))
    		Assert.AreEqual(2, Triangle.GetRow(2))
    		Assert.AreEqual(2, Triangle.GetRow(3))
    		Assert.AreEqual(3, Triangle.GetRow(4))
    		Assert.AreEqual(3, Triangle.GetRow(8))
    		Assert.AreEqual(4, Triangle.GetRow(9))
    		Assert.AreEqual(4, Triangle.GetRow(15))
    		Assert.AreEqual(5, Triangle.GetRow(16))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetColumnTest()
    		Assert.AreEqual(0, Triangle.GetColumn(0))
    		Assert.AreEqual(-1, Triangle.GetColumn(1))
    		Assert.AreEqual(0, Triangle.GetColumn(2))
    		Assert.AreEqual(1, Triangle.GetColumn(3))
    		Assert.AreEqual(-2, Triangle.GetColumn(4))
    		Assert.AreEqual(-1, Triangle.GetColumn(5))
    		Assert.AreEqual(0, Triangle.GetColumn(6))
    		Assert.AreEqual(1, Triangle.GetColumn(7))
    		Assert.AreEqual(2, Triangle.GetColumn(8))
    		Assert.AreEqual(-3, Triangle.GetColumn(9))
    		Assert.AreEqual(2, Triangle.GetColumn(14))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetDistanceTest()
    		Assert.AreEqual(1.528, Triangle.GetDistance(7, 0))
    		Assert.AreEqual(1.528, Triangle.GetDistance(2, 8))
    		Assert.AreEqual(0.577, Triangle.GetDistance(10, 9))
    		Assert.AreEqual(0.577, Triangle.GetDistance(10, 11))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetDistanceTestMore()
    		Assert.AreEqual(0.0, Triangle.GetDistance(7, 7))
    		Assert.AreEqual(1.0, Triangle.GetDistance(10, 12))
    
    		Dim distance As Double
    
    		distance = Math.Round(2 * (Triangle.GetHeight() - Triangle.GetCenterDistance()), 3)
    		Assert.AreEqual(distance, Triangle.GetDistance(2, 6))
    
    		distance = Math.Round(2 * Triangle.GetCenterDistance(), 3)
    		Assert.AreEqual(distance, Triangle.GetDistance(0, 2))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub HugeNumberTest()
    		Assert.AreEqual(0.577, Triangle.GetDistance(2147483646, 2147483647))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub InputOutputTest()
    		Dim input As String
    
    		input = "0 7"
    		Assert.AreEqual("1.528", ModuleMain.Run(input))
    		input = "2 8"
    		Assert.AreEqual("1.528", ModuleMain.Run(input))
    		input = "9 10"
    		Assert.AreEqual("0.577", ModuleMain.Run(input))
    		input = "10 11"
    		Assert.AreEqual("0.577", ModuleMain.Run(input))
    	End Sub
    
    End Class

Mastojun

문제 풀이

각 집들의 상대 거리를 측정한후 피타고라스 정의에 의해 구함.
홀수번째 줄이냐 짝수번째 줄이냐에 따라서 생각해줘야할 변수가 많았다. ㅠㅠ

소스

    #include <stdio.h>
    #include <math.h>
    
    #define square(x) ((x)*(x))
    #define MIN(x, x2, y, y2) ((x)>(y)?(y+y2):(x+x2))
    #define ABS(x) ((x)>0?(x):-(x))
    
    int GetLine(int n)
    {
    	return (int)floor(sqrt((double)n));
    }
    
    double GetResult(int n, int m)
    {
    	double x, y;
    
    	int LineN  = GetLine(n);
    	int LineM  = GetLine(m);
    
    	int PositN = n - square(LineN) - LineN;
    	int PositM = m - square(LineM) - LineM;
    
    	int difX = ABS(PositN - PositM);
    	int difY = ABS(LineN - LineM);
    
    	x = difX / 2.0;
    
    	y = (difY / 2) * sqrt(3.0);
    	
    	if( difY & 1 )
    	{
    		if( MIN(LineN,PositN, LineM,PositM) & 1 )
    		{
    			y += 2*sqrt(3.0)/3;
    		}
    		else
    		{
    			y += sqrt(3.0)/3;
    		}
    	}
    
    	if( difX & 1 )
    	{
    		if( MIN(LineN,PositN, LineM,PositM) & 1 )
    		{
    			if( difY & 1 )	y -= sqrt(3.0)/6;
    			else		y += sqrt(3.0)/6;
    		}		
    		else
    		{
    			if( difY & 1 )	y += sqrt(3.0)/6;
    			else		y -= sqrt(3.0)/6;
    		}
    	}
    
    	return sqrt(x*x + y*y);
    }
    
    int main()
    {
    	int n, m;
    
    	while( scanf("%d %d", &n, &m) == 2 )
    	{
    		printf("%.3lf\n", GetResult(n, m));
    	}
    
    	return 0;
    }

Outbreak

문제 요약

정삼각형 그리드에서 두 지점간 거리 구하는 문제!

문제 해결

(Row, Col) 그리드를 (x, y) 실수 좌표계로 변환
- Row 는 n * n 으로 구하고
- Col 은 구하지 않음.
- 역삼각형으로 돌려서 1,2 사분면 사용.
각 (x,y) 좌표간 거리를 구한다.

소감

IF 가 거슬리지만.. 패스..
이번 주는 이거 한 문제만.. ^^;

풀이

    // "Dermuba Triangle" Solution By Outbreak 
    
    #include <iostream>
    #include <iomanip>
    #include <cmath>
    
    using namespace std;
    
    //#define _TDD
    
    
    // 1 + 2 + 3 + 4 + 5...     = n(n+1) / 2
    //     1 + 2 + 3 + 4 + 5... = (n-1)n / 2
    //--------------------------------------
    // 1 + 3 + 5 + 7 + 9 ...    = n * n
    
    // 1   4   9   12  21       = 각 행의 첫 숫자
    
    // 역삼각형으로 뒤집어서 풀이
    
    
    //---------------------------------------------------------------------------
    
    namespace Solver
    {
    
    	// 정삼각형 한변의 길이
    	static const double WIDTH	= 1;
    	// 정삼각형 높이
    	static const double HEIGHT	= sqrt((double)3) / 2;
    	// 정삼각형 꼭지점에서 외심까지 긴 길이
    	static const double UPPER_HEIGHT= HEIGHT * 2 / 3; 
    	// 정삼각형 꼭지점에서 외심까지 짧은 길이
    	static const double LOWER_HEIGHT= HEIGHT * 1 / 3; 
    	
    
    	// * 좌표 변환기
    	class Converter
    	{
    	public:
    		Converter(int value)
    		{	
    			X = GetX(value);
    			Y = GetY(value);
    		}
    
    		static double GetX(int value)
    		{
    			int distance = GetColDistace(value);
    			
    			return distance * WIDTH / 2;
    		}
    
    		static double GetY(int value)
    		{
    			int row = GetRow(value);
    			int distance = GetColDistace(value);
    
    			double y = HEIGHT * row;
    			
    			if( row & 1 )
    			{
    				if( distance & 1 )
    				{
    					y += UPPER_HEIGHT;
    				}
    				else
    				{
    					y += LOWER_HEIGHT;
    				}
    			}
    			else
    			{
    				if( distance & 1 )
    				{
    					y += LOWER_HEIGHT;
    				}
    				else
    				{
    					y += UPPER_HEIGHT;
    				}
    			}
    
    			return y;
    		}
    		
    		// Row 구하기 - 몇 번째 줄에 있냐? 
    		static int GetRow(int value)
    		{			
    			if( value <= 0 )
    				return 0;
    
    			return (int)sqrt((double)(value));
    		}
    
    		// 해당 Row 의 중간 삼각형 Column
    		static int GetCenterCol(int value)
    		{
    			double row = GetRow(value);
    			double center = (((row+1)*(row+1)-1) + row*row) / 2 ;
    
    			return (int)center;			
    		}
    
    		// 해당 Row 의 중간 삼각형과의 Column 수 차이
    		static int GetColDistace(int value)
    		{
    			int center = GetCenterCol(value);
    			int distance = center - value;
    
    			return distance;
    		}
    	
    	public:
    		double X, Y;
    	};
    
    
    	// * 집 - 좌표간 거리 계산기
    	class House
    	{
    	public:
    		House(double x, double y) : x(x), y(y) {}
    		
    		double operator- (const House& rhs)
    		{
    			double xx = this->x - rhs.x;
    			double yy = this->y - rhs.y;
    			return sqrt(xx*xx + yy*yy); 
    		}
    		
    	private:
    		double x, y;		
    	};	
    
    
    	// * 답 구하기
    	double Calculate(int n, int m)
    	{			
    		// 1. > 정수 (Row, Col) 그리드를 실수 (X, Y) 좌표계로 변환한다.
    		Converter c1(n), c2(m);
    		
    		// 2. > X, Y 좌표계를 쓰는 집을 만든다.
    		House h1(c1.X, c1.Y), h2(c2.X, c2.Y);
    
    		// 3. > 두 집간에 거리를 구한다.
    		return h1 - h2;
    	}
    }
    
    //---------------------------------------------------------------------------
    
    namespace Runner
    {
    	void Execute(istream& in, ostream& out)
    	{
    		int n = 0, m = 0;
    
    		while( in >> n >> m )
    		{		
    			if( in.fail() )
    				break;			
    			
    			out << setprecision(3) << fixed << Solver::Calculate(n,m) << endl;
    		}
    	}
    }
    
    //---------------------------------------------------------------------------
    
    #ifdef _TDD
    
    #include "unittest++.h"
    using namespace Solver;
    
    TEST(Converter_GetRow)
    {
    	// (Row, Col) 정수 그리드 좌표계
    	CHECK_EQUAL(0, Converter::GetRow(0));
    	CHECK_EQUAL(1, Converter::GetRow(1));
    	CHECK_EQUAL(2, Converter::GetRow(4));
    	CHECK_EQUAL(2, Converter::GetRow(7));
    	CHECK_EQUAL(2, Converter::GetRow(8));
    	CHECK_EQUAL(3, Converter::GetRow(9));
    	CHECK_EQUAL(3, Converter::GetRow(11));	
    }
    
    TEST(Converter_GetCol)
    {
    	// (Row, Col) 정수 그리드 좌표계
    	CHECK_EQUAL(6, Converter::GetCenterCol(4));
    
    	CHECK_EQUAL(2, Converter::GetColDistace(4));
    	CHECK_EQUAL(-2, Converter::GetColDistace(8));
    	CHECK_EQUAL(-1, Converter::GetColDistace(3));
    }
    
    TEST(Converter_GetX)
    {
    	// (X, Y)  실수 좌표계
    	CHECK_CLOSE( 0,		Converter::GetX(0), 0.001);
    	CHECK_CLOSE( 0.5,	Converter::GetX(1), 0.001);
    	CHECK_CLOSE( -0.5,	Converter::GetX(3), 0.001);
    	CHECK_CLOSE( 1,		Converter::GetX(4), 0.001);
    	CHECK_CLOSE( -1,	Converter::GetX(8), 0.001);
    
    }
    
    TEST(Converter_GetY)
    {
    	// (X, Y)  실수 좌표계
    	CHECK_CLOSE( HEIGHT * Converter::GetRow(6) + UPPER_HEIGHT, Converter::GetY(6), 0.001 );
    	CHECK_CLOSE( HEIGHT * Converter::GetRow(0) + UPPER_HEIGHT, Converter::GetY(0), 0.001 );
    	
    	CHECK_CLOSE( HEIGHT * Converter::GetRow(2) + UPPER_HEIGHT / 2, Converter::GetY(2), 0.001 );
    }
    
    TEST(House)
    {
    	House h1(0,0), h2(3,4);
    	CHECK_EQUAL( 5, h1-h2);
    }
    
    TEST(Output1)
    {
    	stringstream input;
    	stringstream output;
    
    	input << "0 7\n";
    
    	Runner::Execute(input, output);
    
    	CHECK_EQUAL("1.528\n", output.str());
    }
    
    TEST(Output)
    {
    	stringstream input;
    	stringstream output;
    
    	input <<
    		"0 7\n"
    		"2 8\n"
    		"9 10\n"
    		"10 11\n";
    
    	Runner::Execute(input, output);
    
    	CHECK_EQUAL("1.528\n1.528\n0.577\n0.577\n", output.str());
    }
    
    #endif
    
    //---------------------------------------------------------------------------
    
    int main()
    {
    
    #ifdef _TDD	
    	UnitTest::RunAllTests();
    #else
    	Runner::Execute(cin, cout);
    #endif // _TDD
    	return 0;
    
    }

ParkPD

Wrong Answer 나오네요. 문제가 될만한 테스트 케이스 있으면 좀 알려주세요. [ParkPD]

ios설정값을 바꿔서 소수부 정밀도를 높이거나 printf를 사용해서 출력해보세요. [itmentor]

  /* @JUDGE_ID:parkpd 110401 Cpp "test" */
  
  /* @BEGIN_OF_SOURCE_CODE */
  
  #include <iostream>
  #include <vector>
  #include <set>
  #include <deque>
  #include <list>
  #include <stack>
  #include <string>
  #include <algorithm>
  #include <map>
  #include <limits>
  #include <assert.h>
  #include <iomanip>
  #include <complex>
  #include <math.h>
  
  //#define _UNIT_TEST
  
  #ifdef _UNIT_TEST
  #include <Windows.h>
  #include "../UnitTest++/src/UnitTest++.h"
  #endif
  
  using namespace std;
  
  #ifdef max
  #undef max
  #endif
  
  #ifdef min
  #undef min
  #endif
  
  // Minimum Spanning Tree -> Prim Algorithm 을 생각하며 풀었음.
  
  namespace ATUtil
  {
  	bool IsInRange(int value, int from, int to)
  	{
  		return (from <= value) && (value <= to);
  	}
  
  	int ConvertToIndex(char c)
  	{
  		if ('a' <= c && c <= 'z')
  		{
  			return c - 'a';
  		}
  		else
  		{
  			return -1;
  		}
  	}
  
  	char ConvertToChar(int i)
  	{
  		return (char)i + 'a';
  	}
  
  #ifdef _UNIT_TEST
  	class CStopWatch
  	{
  	public:
  		CStopWatch()
  		{
  			m_StartTick = GetTickCount();		// gcc 에서 안 될 수 있으니까
  		}
  
  		~CStopWatch()
  		{
  			cout << "Time passed : " << GetTickCount() - m_StartTick << " milisec.\n";
  		}
  
  		int m_StartTick;
  	};
  #endif
  
  	typedef map<int, int> IntDB;
  	typedef vector<int> Ints;
  	typedef list<int> IntList;
  
  };
  
  using namespace ATUtil;
  
  #ifdef _UNIT_TEST
  
  int main()
  {
  	UnitTest::RunAllTests();
  
  	char temp;
  	cin >> temp;
  
  	return 0;
  }
  
  #endif
  
  // code implement
  
  namespace ATCode
  {
  	///////////////////////////////////////////////////////////////
  	// CSolver
  	class CSolver
  	{
  	public:
  		void GetXY(int n, int& x, int& y)
  		{
  			if (0 == n)		// 원점
  			{
  				x = 0;
  				y = 0;
  				return;
  			}
  
  			// 최적화 1 번.
  			//int comp = 1;
  			//while (comp * comp <= n)
  			//{
  			//	++comp;
  			//}
  			//y = comp - 1;
  			y = (int)sqrt((double)n);
  
  			int width = y * 2 + 1;
  			int midValue = (y * y) + width / 2;
  			x = n - midValue;
  		}
  
  		double Input(int from, int to)
  		{
  			int x1, y1, x2, y2;
  			GetXY(from, x1, y1);
  			GetXY(to, x2, y2);
  
  			// x 차이는 0.5 km
  			// 삼각형 높이는 0.866025 km			
  			// 외심(circumcenter) 중 긴 거리는 0.577350, 짧은 거리는 0.288675
  			// 각 꼭지점과 외심을 잇는 선을 그어, 작은 직각 삼각형 3개가 만들어졌을 때,
  			// c 는 빗면, b 는 밑면, a 는 높이
  			// h 는 길이 1 km 의 정삼각형의 높이.
  			const double a = 0.288675;
  			const double b = 0.5;
  			const double c = 0.577350;			
  			const double h = a + c;
  
  			int offsetX = abs(x1 - x2);
  			int offsetY = abs(y1 - y2);
  			int manhattanDist = offsetX + offsetY;
  
  			double diffX = (double)offsetX * b;
  			double diffY = 0.0;
  			if (0 == manhattanDist % 2)		// 같은 높이(바닥에 가까운 점)
  			{
  				diffY = offsetY * h;
  			}
  			else
  			{
  				if (0 == offsetY)
  				{
  					diffY = (c - a);
  				}
  				else
  				{
  					if (0 == y1 % 2)
  					{
  						diffY = (offsetY - 1) * h + (2 * a);
  					}
  					else
  					{
  						diffY = (offsetY - 1) * h + (2 * c);
  					}
  				}				
  			}
  
  			double ret = sqrt(diffX * diffX + diffY * diffY);
  
  			// 소수점 4째 자리에서 반올림하기.
  			ret = ((int)((ret * 1000.0) + 0.5)) * 0.001;
  			return ret;
  		}
  
  		vector<int> m_Levels;
  	};
  
  	///////////////////////////////////////////////////////////////
  	// CConsole
  	class CConsole
  	{
  	public:
  		static void ConsoleTest(istream& input, ostream& output);
  	};
  
  	void CConsole::ConsoleTest(istream& input, ostream& output)
  	{
  		CSolver s;
  		int from, to;
  		while (input >> from >> to)
  		{
  			output << s.Input(from, to) << '\n';
  		}
  	};
  }
  
  using namespace ATCode;
  
  #ifndef _UNIT_TEST
  
  int main()
  {
  	CConsole::ConsoleTest(cin, cout);
  
  	return 0;
  }
  
  #else
  
  // tests
  
  struct FixtureBase
  {
  	FixtureBase()
  	{
  	}
  
  	int x, y;
  	stringstream input;
  	stringstream output;
  };
  
  TEST_FIXTURE(FixtureBase, GetXY)
  {
  	CSolver g;
  	int tests[] = {
  		0, 0, 
  		-1, 1, 
  		0, 1, 
  		1, 1, 
  		-2, 2
  	};
  	for (int i = 0; i < sizeof(tests) / sizeof(int); i += 2)
  	{
  		//cout << i / 2 << '\n';
  		g.GetXY(i / 2, x, y);
  		CHECK_EQUAL(tests[i], x);
  		CHECK_EQUAL(tests[i + 1], y);
  	}
  }
  
  TEST_FIXTURE(FixtureBase, Input)
  {
  	CSolver g;
  	double tests[] = {
  		0, 7, 1.528,
  		2, 8, 1.528,
  		9, 10, 0.577,
  		10, 11, 0.577,
  		7, 7, 0.0,
  		10, 12, 1.0,
  		2147483646, 2147483647, 0.577
  	};
  
  	for (int i = 0; i < sizeof(tests) / sizeof(double); i += 3)
  	{
  		cout << "Test Input : " << i / 3 << '\n';
  		CHECK_CLOSE(tests[i + 2], g.Input((int)tests[i], (int)tests[i + 1]), 0.001);
  	}
  }
  
  TEST_FIXTURE(FixtureBase, ConsoleTest)
  {
  	input << 
  		"0 7\n"
  		"2 8\n"
  		"9 10\n"
  		"10 11\n"
  		;
  	CConsole::ConsoleTest(input, output);
  	CHECK_EQUAL( 
  		"1.528\n"
  		"1.528\n"
  		"0.577\n"
  		"0.577\n",
  		output.str());
  }
  
  #endif
  
  /* @END_OF_SOURCE_CODE */

itmentor

C++버전 Accept

1차 시도 : 모든 데이터 타입을 float로 사용 --> Wrong Answer
2차 시도 : 데이터 타입을 double로 사용 --> Wrong Answer

3차 시도 : 출력 부분을 std::cout에서 printf로 바꿈 --> Solved

cout은 기본적으로 실수를 float형으로 처리하나봅니다. printf를 사용하면 됩니다. ios값을 바꿔도 될듯...

정수부의 값이 커지면 float의 소수부의 표현범위가 작아집니다.

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

#ifdef _UNIT_TEST
	#include <unittest++.h>
#endif

const long double  PI = 3.14159265358979323846;
const long double  BaseX = cos( (1.0 / 3.0) * PI );
const long double  BaseY = sin( (1.0 / 3.0) * PI );


struct Point
{
	double x,y;
	double distance(Point& pt)
	{
		return sqrt( (pt.x - x) * (pt.x - x) + (pt.y - y) * (pt.y - y) );
	}
};

std::vector<unsigned long> calculateBaseColumn(unsigned long limitValue)
{
	std::vector<unsigned long> arr;
	
	unsigned long nextBaseY = 0;
	for(unsigned long i = 1 ; nextBaseY <= limitValue; i++)
	{
		arr.push_back(nextBaseY);
		nextBaseY = arr[ arr.size() - 1 ] + i * 2;
	}

	return arr;
}

Point CalculateTriangleCenter( Point* triangleVertices )
{
	Point center;
	center.x = triangleVertices[0].x + triangleVertices[1].x + triangleVertices[2].x;
	center.y = triangleVertices[0].y + triangleVertices[1].y + triangleVertices[2].y;

	center.x /= 3;
	center.y /= 3;
	return center;
}

void searchRow(std::vector<unsigned long>& array, unsigned long address, unsigned long & localX, unsigned long & localY )
{
	unsigned long i = 0;
	for( ; i < array.size() - 1 ; i++)
	{
		if( array[i] <= address && address <= array[i+1] )
		{
			break;
		}
	}

	unsigned long leftIndex = i;
	unsigned long rightIndex = i + 1;
	unsigned long leftValue = array[leftIndex];
	unsigned long rightValue = array[rightIndex];


	if( leftValue <= address && address <= leftValue + leftIndex )
	{
		localX = address - leftValue;
		localY = leftIndex;
	}
	else if( rightValue - rightIndex <= address && address <= rightValue)
	{
		localX = -(rightValue - address);
		localY = rightIndex;
	}
}

void convertLocalToGlobal( int x, int y, Point& a, Point& b, Point& c)
{
	if( abs(x+y) % 2 == 0 )	//짝수
	{
		a.x = x;
		a.y = y;

		b.x = x - 1;
		b.y = y + 1;

		c.x = x + 1;
		c.y = y + 1;
	}
	else			//홀수
	{
		a.x = x;
		a.y = y + 1;

		b.x = x - 1;
		b.y = y;

		c.x = x + 1;
		c.y = y;
	}
}


void GetTriangleCoordinate(Point& a, Point& b, Point& c, Point* output)
{
	output[0].x = BaseX * a.x;
	output[0].y = BaseY * a.y;

	output[1].x = BaseX * b.x;
	output[1].y = BaseY * b.y;

	output[2].x = BaseX * c.x;
	output[2].y = BaseY * c.y;
}


double GetDistance(std::vector<unsigned long>& array, unsigned long beginTriangle, unsigned long endTriangle )
{
	unsigned long beginLocalX, beginLocalY;
	searchRow(array, beginTriangle, beginLocalX, beginLocalY );
	Point beginA, beginB, beginC;
	convertLocalToGlobal(beginLocalX, beginLocalY, beginA,beginB,beginC);
	Point beginLastPosition[3];
	GetTriangleCoordinate(beginA,beginB,beginC, beginLastPosition);
	Point beginCenter = CalculateTriangleCenter(beginLastPosition);

	unsigned long endLocalX, endLocalY;
	searchRow(array, endTriangle, endLocalX, endLocalY );
	Point endA, endB, endC;
	convertLocalToGlobal(endLocalX, endLocalY, endA,endB,endC);
	Point endLastPosition[3];
	GetTriangleCoordinate(endA,endB,endC, endLastPosition);
	Point endCenter = CalculateTriangleCenter(endLastPosition);

	return endCenter.distance(beginCenter);
}


int main()
{
#ifdef _UNIT_TEST
	UnitTest::RunAllTests();
#endif

	std::vector< unsigned long > baseCoordinateArray;
	baseCoordinateArray = calculateBaseColumn(3000000000);

	while(true)
	{
		char ln[512];
		std::cin.getline(ln,512);

		if( ln[0] == 0 )
			break;
		
		long beg,end;
		sscanf(ln, "%ld %ld", &beg, &end);

		double distance = GetDistance(baseCoordinateArray, beg,end);
		distance += 0.0005;
		distance *= 1000;
		distance = (int)distance;
		distance /= 1000;
		printf("%.3lf\n", distance);
	}	

	return 0;
}

#ifdef _UNIT_TEST
TEST(TriangleG)
{
	Point pt[3] = { 0, 0, -BaseX, -BaseY, BaseX, -BaseY };
	Point center = CalculateTriangleCenter(pt);

	CHECK_CLOSE( 0, center.x, 0.001f );
	CHECK_CLOSE( -0.57735f, center.y, 0.0005f );

	Point pt2[3] = { 0, -2*BaseY, -BaseX, -BaseY, BaseX, -BaseY };

	Point center2 = CalculateTriangleCenter(pt2);
	CHECK_CLOSE( 0, center2.x, 0.001f );
	CHECK_CLOSE( -0.57735f * 2, center2.y, 0.0005f );

	double distance = center.distance(center2);
	CHECK_CLOSE( 0.577f, distance, 0.0005f );
}

TEST(calculateBaseColumn)
{
	std::vector< unsigned long > baseCoordinateArray;
	baseCoordinateArray = calculateBaseColumn(3000000000);

	CHECK_EQUAL( baseCoordinateArray[0], 0 );
	CHECK_EQUAL( baseCoordinateArray[1], 2 );
	CHECK_EQUAL( baseCoordinateArray[2], 6 );
	CHECK_EQUAL( baseCoordinateArray[3], 12 );
}

TEST(searchRow)
{
	std::vector< unsigned long > baseCoordinateArray;
	baseCoordinateArray = calculateBaseColumn(3000000000);

	unsigned long localX, localY;
	searchRow(baseCoordinateArray, 0, localX, localY );
	CHECK_EQUAL( 0, localX);
	CHECK_EQUAL( 0, localY);

	searchRow(baseCoordinateArray, 8, localX, localY );
	CHECK_EQUAL( 2, localX);
	CHECK_EQUAL( 2, localY);

	searchRow(baseCoordinateArray, 9, localX, localY );
	CHECK_EQUAL( -3, localX);
	CHECK_EQUAL( 3, localY);
}

TEST( convertLocalToGlobal )
{
	std::vector< unsigned long > baseCoordinateArray;
	baseCoordinateArray = calculateBaseColumn(3000000000);

	Point a,b,c;
	//<0>
	convertLocalToGlobal(0, 0, a,b,c);
	CHECK_CLOSE( a.x, 0, 0.001f );
	CHECK_CLOSE( a.y, 0, 0.001f );
	CHECK_CLOSE( b.x, -1, 0.001f );
	CHECK_CLOSE( b.y, 1, 0.001f );
	CHECK_CLOSE( c.x, 1, 0.001f );
	CHECK_CLOSE( c.y, 1, 0.001f );

	//<2>
	convertLocalToGlobal(0, 1, a,b,c);
	CHECK_CLOSE( a.x, 0, 0.001f );
	CHECK_CLOSE( a.y, 2, 0.001f );
	CHECK_CLOSE( b.x, -1, 0.001f );
	CHECK_CLOSE( b.y, 1, 0.001f );
	CHECK_CLOSE( c.x, 1, 0.001f );
	CHECK_CLOSE( c.y, 1, 0.001f );

	//<3>
	convertLocalToGlobal(1, 1, a,b,c);
	CHECK_CLOSE( a.x, 1, 0.001f );
	CHECK_CLOSE( a.y, 1, 0.001f );
	CHECK_CLOSE( b.x, 0, 0.001f );
	CHECK_CLOSE( b.y, 2, 0.001f );
	CHECK_CLOSE( c.x, 2, 0.001f );
	CHECK_CLOSE( c.y, 2, 0.001f );

	//<5>
	convertLocalToGlobal(-1, 2, a,b,c);
	CHECK_CLOSE( a.x, -1, 0.001f );
	CHECK_CLOSE( a.y, 3, 0.001f );
	CHECK_CLOSE( b.x, -2, 0.001f );
	CHECK_CLOSE( b.y, 2, 0.001f );
	CHECK_CLOSE( c.x, 0, 0.001f );
	CHECK_CLOSE( c.y, 2, 0.001f );
}

TEST(GetTriangleCoordinate)
{
	std::vector< unsigned long > baseCoordinateArray;
	baseCoordinateArray = calculateBaseColumn(3000000000);

	Point a,b,c;
	convertLocalToGlobal(0, 0, a,b,c);

	Point pt[3];
	GetTriangleCoordinate(a,b,c, pt);
	Point center = CalculateTriangleCenter(pt);

	CHECK_CLOSE( 0, center.x, 0.001f );
	CHECK_CLOSE( 0.57735f, center.y, 0.0005f );

	Point pt2[3] = {a,b,c};
	convertLocalToGlobal(0, 1, a,b,c);
	GetTriangleCoordinate(a,b,c, pt2);

	Point center2 = CalculateTriangleCenter(pt2);
	CHECK_CLOSE( 0, center2.x, 0.001f );
	CHECK_CLOSE( 0.57735f * 2, center2.y, 0.0005f );

	double distance = center.distance(center2);
	CHECK_CLOSE( 0.577f, distance, 0.0005f );
}

TEST(GetTriangleDistance)
{
	std::vector< unsigned long > baseCoordinateArray;
	baseCoordinateArray = calculateBaseColumn(3000000000);

	double distance = GetDistance(baseCoordinateArray, 0,7);
	CHECK_CLOSE( 1.528f, distance, 0.0005f );

	distance = GetDistance(baseCoordinateArray, 2,8);
	CHECK_CLOSE( 1.528f, distance, 0.0005f );

	distance = GetDistance(baseCoordinateArray, 9,10);
	CHECK_CLOSE( 0.577f, distance, 0.0005f );

	distance = GetDistance(baseCoordinateArray, 10,11);
	CHECK_CLOSE( 0.577f, distance, 0.0005f );
}
#endif

algorithm dermuba triangle - andstudy/forge GitHub Wiki

CynicJJ

!ModuleMain.vb

Triangle.vb

!TriangleTest.vb

Mastojun

문제 풀이

소스

Outbreak

문제 요약

문제 해결

소감

풀이

ParkPD

itmentor

C++버전 Accept

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️