hiho一下 第125周 GeoHash一·編碼解碼

題目1 : GeoHash一·編碼解碼

時間限制: 10000ms 單點時限: 1000ms 記憶體限制: 256MB

描述

小Hi：上一次我們講到了在一個城市裡，利用四叉樹來查找一個坐标附近的點。假如我們把範圍擴大到整個地球呢？

小Ho：擴大到整個地球，那坐标怎麼辦？

小Hi：坐标的話，我們就用經緯度好了。緯度從-90°到90°，經度從-180°到180°。

小Ho：四叉樹裡面我們用的都是整數坐标，如果變成實數坐标感覺就不那麼容易了。

小Hi：沒錯，而且在擴充到全球的情況下，可以預見點數也會變得非常巨大。是以用四叉樹來存儲這麼多點顯然不太現實。

小Ho：那有什麼好一點的方法麼？

小Hi：當然有了，這一次我們采用編碼的方式來解決。

提示：geohash

輸入

第1行：2個整數N,M。1≤N,M≤100。

第2..N+1行：每行2個實數x,y，第i+1行表示第i個點的緯度和經度。-90≤x≤90，-180≤y≤180

第N+2..N+M+1行：每行1個字元串，表示需要解碼的geohash代碼

輸出

第1..N行：每行1個字元串，第i行表示以第i個點的geohash編碼，長度為10。

第N+1..N+M行：每行2個實數x,y，第N+i行表示以第i個geohash編碼所表示的區域中心點坐标，保留6位小數。

樣例輸入

3 2
36.255833 117.103367
27.293056 112.688922
34.477861 110.082600
wx0csn0ng82y
ww0k7k0et784      

樣例輸出

ww7q2b0jd1
wsb5k299d4
wqnk0ux8n7
39.672792 113.730620
34.519663 112.995297      

#include<bits/stdc++.h>
using namespace std;


char Base32[]=
{
    '0','1','2','3','4','5','6','7','8','9','b','c','d','e','f','g','h','j','k','m','n','p','q','r','s','t','u','v','w','x','y','z'
};

string encode(double latt,double lonn,int precision)
{
    double lat[]= {-90,90};
    double lon[]= {-180,180};
    int len =precision*5;
    string geohash;
    int bits=0;
    for(int i=1; i<=len; i++)
    {
        if (i&1)
        {
            double mid=(lon[0]+lon[1])/2;
            if (lonn>mid)
                bits=bits<<1|1,lon[0]=mid;
            else
                bits<<=1,lon[1]=mid;
        }
        else
        {
            double mid=(lat[0]+lat[1])/2;
            if (latt>mid)
                bits=bits<<1|1,lat[0]=mid;
            else
                bits<<=1,lat[1]=mid;
        }
        if (i%5==0)
            geohash+=Base32[bits],bits=0;
    }
    return geohash;

}
int indexofBase32(char s)
{
    return lower_bound(Base32,Base32+32,s)-Base32;
}
void decode(char  s[],double &x,double&y)
{
    bool odd=1;
    double lat[]= {-90,90};
    double lon[]= {-180,180};
    double mid;
    int len=strlen(s);
    for(int i=0; i<len; i++)
    {

        int bits=indexofBase32(s[i]);
        for(int j=4; j>=0; j--)
        {
                int bit=(bits>>j)&1;
            if (odd&1)
            {
                mid=(lon[0]+lon[1])/2;
                lon[1-bit]=mid;
            }
            else
            {
                mid=(lat[0]+lat[1])/2;
                lat[1-bit]=mid;
            }
            odd^=1;
        }
    }
    x=(lat[0]+lat[1] )/2;
    y=(lon[0]+lon[1] )/2;
}
int main()
{
    double x,y;
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        scanf("%lf%lf",&x,&y);
        string ret=encode(x,y,10);
        printf("%s\n",ret.c_str());
    }
    char ss[15];
    for(int i=1; i<=n; i++)
    {
        scanf("%s",ss);
        decode(ss,x,y);
        printf("%.6lf %.6lf\n",x,y);
    }


}