UVa 587 There's treasure everywhere!

解題策略

給一張藏寶圖，記載著如何找到寶藏的指令，要算出最終寶藏的確切位置跟及離出發點的距離。這題是典型的模擬題，照著題目要求在平面座標上四處移動就行了。

我在兩個地方稍微傷了點腦筋

1. 這題的input parsing不好做，或者說用c++ std IO有點麻煩。
   operator>>切字串時不能選擇delimeter，用getline 來切也不能設定超過一個delimeter，可是這題偏偏就有兩個-逗點跟句點。我不想自己切，最後就把字串內的逗點跟句點都換成空白，這樣就能用上stringstream了。
   
2. 浮點數誤差：這題送去ZJ後，我拿到一個WA結果如下

您的答案為: The treasure is located at (0.000,-0.000).
正確答案為: The treasure is located at (0.000,0.000).

怎麼會有負零呢!?  應該不是負零，是個非常非常小的負數，因為浮點數不夠精確才產生的誤差，加上一個EPS修正就行了。(不過事實上我對EPS的觀念還不是很懂..orz)

解決這兩項大概就沒問題了，AC get。

	/**
	* UVa 587 There's treasure everywhere!
	* Author: chchwy
	* Last Modified: 2010.03.22
	*/
	#include<iostream>
	#include<sstream>
	#include<cmath>
	#include<algorithm>
	using namespace std;
	const double EPS = 0.000000001;
	class Vector2f
	{
	public:
	double x, y;
	Vector2f(double px, double py)
	{
	x = px, y = py;
	}
	Vector2f operator+= ( Vector2f right )
	{
	x += right.x, y += right.y;
	}
	Vector2f operator* ( int c )
	{
	return Vector2f( x * c, y * c );
	}
	double distance(double px, double py)
	{
	double dx = x - px;
	double dy = y - py;
	return sqrt( (dx * dx) + (dy * dy) );
	}
	};
	/* 8 directions */
	const double SQRT2 = sqrt(2) / 2;
	Vector2f N(0, 1);
	Vector2f NE(SQRT2, SQRT2);
	Vector2f E(1, 0);
	Vector2f SE(SQRT2, -SQRT2);
	Vector2f S(0, -1);
	Vector2f SW(-SQRT2, -SQRT2);
	Vector2f W(-1, 0);
	Vector2f NW(-SQRT2, SQRT2);
	bool isComma(char c)
	{
	return (c == ',' || c == '.');
	}
	/* return the treasure location according to line */
	Vector2f findTreasure( string line )
	{
	// replace comma to white-space for stringstream extraction
	replace_if( line.begin(), line.end(), isComma, ' ');
	Vector2f loc(0, 0); //current location
	istringstream sin(line);
	string direct;
	int step;
	while ( sin >> step >> direct )
	{
	//cout<<step<<','<<direct<<endl;
	if ( direct == "N" )
	loc += N * step;
	else if ( direct == "NE" )
	loc += NE * step;
	else if ( direct == "E" )
	loc += E * step;
	else if ( direct == "SE" )
	loc += SE * step;
	else if ( direct == "S" )
	loc += S * step;
	else if ( direct == "SW" )
	loc += SW * step;
	else if ( direct == "W" )
	loc += W * step;
	else if ( direct == "NW" )
	loc += NW * step;
	}
	return loc;
	}
	int main()
	{
	#ifndef ONLINE_JUDGE
	freopen("587.in", "r", stdin);
	#endif
	int mapNo = 1;
	string line;
	while ( getline(cin, line) )
	{
	if ("END" == line)
	break;
	Vector2f target = findTreasure( line );
	printf("Map #%d\n", mapNo++);
	printf("The treasure is located at (%.3lf,%.3lf).\n", target.x + EPS, target.y + EPS );
	printf("The distance to the treasure is %.3lf.\n\n", target.distance(0, 0) );
	}
	return 0;
	}

view raw 587.cpp hosted with ❤ by GitHub