hdoj 無限的路 2073 （數學模拟&預處理&轉換）

無限的路

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 7612    Accepted Submission(s): 3918

Problem Description 甜甜從小就喜歡畫圖畫，最近他買了一支智能畫筆，由于剛剛接觸，是以甜甜隻會用它來畫直線，于是他就在平面直角坐标系中畫出如下的圖形：

甜甜的好朋友蜜蜜發現上面的圖還是有點規則的，于是他問甜甜：在你畫的圖中，我給你兩個點，請你算一算連接配接兩點的折線長度（即沿折線走的路線長度）吧。  

Input 第一個數是正整數N（≤100）。代表資料的組數。

每組資料由四個非負整數組成x1，y1，x2，y2；所有的數都不會大于100。

Output 對于每組資料，輸出兩點(x1,y1),(x2,y2)之間的折線距離。注意輸出結果精确到小數點後3位。  

Sample Input

5
0 0 0 1
0 0 1 0
2 3 3 1
99 99 9 9
5 5 5 5
        

Sample Output

1.000
2.414
10.646
54985.047
0.000
  
  
   //思路：先用map[x][y]表示點（x,y）排在第幾個位置。
  
  
   因為題中說了坐标最大值不超過100，是以最多隻用計算20000多個點之間的距離，是以轉換一下，通過打表求出從（0,0）點到後面每個點（x,y）之間的距離dis[map[x][y]]，接着再求（x1,y1）到（x2,y2）之間的距離l=(fabs)(dis[map[x2][y2]]-dis[map[x1][y1]]).
  
  
   比較簡單，考試時感覺很麻煩，沒寫，考完後20分鐘就解決了T_T。。。，下次不能在眼高手低了。。。
  
  
          
#include<stdio.h>
#include<string.h>
#include<math.h> 
#include<algorithm>
#include<iostream>
#define INF 0x3f3f3f3f
#define IN __int64
#define ull unsigned long long
#define ll long long
#define N 2010
#define M 1007
using namespace std;
int map[210][210];
double dis[100010];
int init()
{
	int i,j,k=0;
	int kk=0;
	int x,y;
	int x1=0,y1=0;
	dis[0]=0;
	while(k<=200)
	{
		for(i=0;i<=k;i++)
		{
			x=i;y=k-i;
			map[x][y]=++kk;//map[x][y]存放的是（x,y）的序号，表示點（x,y）是第kk個輸入點。 
			dis[kk]=dis[kk-1]+(double)(sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1)));
			//dis[kk]存放的是從第0個輸入點(0,0)到第kk個輸入點(x,y)之間的距離 
			x1=x;y1=y;
		}
		k++;
	}
}
int main()
{
	int t,n,m;
	init();
	scanf("%d",&t);
	while(t--)
	{
		int x1,x2,y1,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		double l=fabs(dis[map[x2][y2]]-dis[map[x1][y1]]);
		printf("%.3lf\n",l);
	}
}