UVaLive 7375 Hilbert Sort (递归，四分图，模拟)

时间：2022-11-14 06:17:36

题意：告诉你一条希尔伯特曲线的大小，然后给你n 个人，及n 个人的坐标，你的起点是左下角，终点是右下角，按照希尔伯特的曲线去走，按照这个顺序给n个人排序，

按顺序输出每个人的名字！

析：这就是一个四分图，每次都把当前的图分成四份，左下角的是顺时针旋转，左上角和右上角不变，右下角逆时针旋转90，那么我们就递归这个过程，给所给的人编号，

最后再按编号输出即可。

代码如下：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <map>

#include <cctype>

#include <stack>

using namespace std ;

typedef long long LL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const double inf = 0x3f3f3f3f3f3f;

const double PI = acos(-1.0);

const double eps = 1e-10;

const int maxn = 2e5 + 5;

const int mod = 1e9 + 7;

const char *mark = "+-*";

const int dr[] = {-1, 0, 1, 0};

const int dc[] = {0, 1, 0, -1};

int n, m;

inline int Min(int a, int b){ return a < b ? a : b; }

inline int Max(int a, int b){ return a > b ? a : b; }

inline LL Min(LL a, LL b){ return a < b ? a : b; }

inline LL Max(LL a, LL b){ return a > b ? a : b; }

inline bool is_in(int r, int c){

    return r >= 0 && r < n && c >= 0 && c < m;

}

struct node{

    string id;

    string name;

    bool operator < (const node &p) const{

        return id < p.id;

    }

};

node a[maxn];

string dfs(double x, double y, double s, int d){

    double mid = s / 2;

    string ans;

    if(d >= 1){

        if(x <= mid && y <= mid)  ans = "1" + dfs(y, x, mid, d-1);

        else if(x <= mid && y > mid)  ans = "2" + dfs(x, y-mid, mid, d-1);

        else if(x > mid && y > mid)  ans = "3" + dfs(x-mid, y-mid, mid, d-1);

        else if(x > mid && y <= mid) ans = "4" + dfs(mid-y, s-x, mid, d-1);

    }

    return ans;

}

int main(){

    while(scanf("%d %d", &n, &m) == 2){

        int x, y;

        for(int i = 0; i < n; ++i){

            string s;

            cin >> x >> y >> s;

            a[i].name = s;

            a[i].id = dfs(x, y, m, 30);

        }

        sort(a, a+n);

        for(int i = 0; i < n; ++i)

            cout << a[i].name << endl;

    }

    return 0;

}

　　

　　

相关文章