防卡哈希函数

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

hash:

ll haxi(void)
{
    ll res=0;
    for(int i=1; s[i]; i++)
        res=(res*seed+s[i])%mod;
    return res;
}

题目链接:GeoHash一·编码解码

GeoHash:

char trans(int x)
{
    if(x>=0&&x<=9)return x+'0';
    if(x>=10&&x<=16)return x+88;
    if(x==17||x==18)return x+89;
    if(x==19||x==20)return x+90;
    if(x>=21&&x<=31)return x+91;
}

int getnum(int *a)
{
    return a[0]*16+a[1]*8+a[2]*4+a[3]*2+a[4];
}

void geohash(double x,double y)
{
    int a[60]= {0};
    char res[15]= {0};
    double l=-90.0,r=90.0,mid;
    for(int i=1; i<=25; i++)
    {
        mid=(l+r)/2.0;
        if(x<mid)r=mid;
        else
        {
            a[2*i]=1;
            l=mid;
        }
    }
    l=-180,r=180;
    for(int i=1; i<=25; i++)
    {
        mid=(l+r)/2.0;
        if(y<mid)r=mid;
        else
        {
            a[2*i-1]=1;
            l=mid;
        }
    }
    for(int i=1; i<=50; i+=5)
        printf("%c",trans(getnum(a+i)));
    printf("\n");
}

int retrans(char c)
{
    if(c>='0'&&c<='9')return c-'0';
    if(c>=98&&c<=104)return c-88;
    if(c==106||c==107)return c-89;
    if(c==109||c==110)return c-90;
    if(c>=112&&c<=122)return c-91;
}

void fillnum(int x,int *res)
{
    res[0]=x/16,x%=16;
    res[1]=x/8,x%=8;
    res[2]=x/4,x%=4;
    res[3]=x/2,x%=2;
    res[4]=x;
}

void regeohash(char *a)
{
    int temp[70]={0},t;
    for(int i=1;i<=10;i++)
    {
        t=retrans(a[i]);
        fillnum(t,temp+i*5-4);
    }
    double la=-90,ra=90,lb=-180,rb=180;
    for(int i=1;i<=50;i++)
    {
        if(!(i&1))
        {
            double mid=(la+ra)/2.0;
            if(temp[i])la=mid;
            else ra=mid;
        }
        else
        {
            double mid=(lb+rb)/2.0;
            if(temp[i])lb=mid;
            else rb=mid;
        }
    }
    double lat=(la+ra)/2.0,lon=(lb+rb)/2.0;
    printf("%.6lf %.6lf\n",lat,lon);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    while(n--)
    {
        double x,y;
        scanf("%lf%lf",&x,&y);
        geohash(x,y);
    }
    while(m--)
    {
        char a[20]={0};
        scanf("%s",a+1);
        regeohash(a);
    }
    return 0;
}