复习一下坐标转换 - O興~ - 歪酷博客 Ycool Blog

UVA#10206（与UVA#316完全相同，但是316的测试数据更严密）是一道很有意思的题，题目描述如下：（原版：http://online-judge.uva.es/p/v3/316.html）

给你一张星相图，其中最多1000颗星，每颗星的坐标x、y值都是整数。再给你一个星座的草图，其中有若干颗星，每颗星的坐标也都是整数。问你这个星座在这个星相图中出现了几次。只要星相图中的某一个子集与星座的草图经过任意的旋转、缩放的结果能够重合，那么就认为星座在图中出现了一次。

算法很简单，一个字，搜。对于星相图中的每两颗星A、B，把它们看作是星座中的前两颗星a、b。根据{A, B}、{a, b}这两对点，就可以算出旋转的角度和缩放比例了。然后把星座中所有其它的星都按照同样的变换映射到星相图中，看图中是否存在这些星。如果全都存在，则找到了一次出现。说起来简单，但是这题有两个要注意的地方：

1.精度问题。由于星相图上的坐标都是整数，所以只要星座经过坐标转换后有任何一颗星的坐标不是整数，那么就不可能出现在图中。但是角度的sin、cos等值都是浮点数，难免会损失精度，所以就很难判结果到底是不是整数。
我的解决方法是，化简公式　+　分子和分母分开运算。我们先来复习一下坐标变换的公式。前面的算法里提到的“两对点”，也就是星座中的前两颗星和星相图中的任意两颗星，我们可以把它们看作是两个向量，所以我们就可以用向量夹角的公式：
假设从向量v1:{x1,y1}转到向量v2:{x2,y2}的夹角为A，则：

也就是两个向量的点积（dot product）除以两个向量的模之积。cos A一定 >= 0，因为夹角不超过180度。

也就是两个向量的叉积（cross product）除以两个向量的模之积。sin A有正有负，因为从v1转到v2有可能是从逆时针方向，也可能是顺时针方向（这时A是个负角）。这一点就可以从向量的叉积中体现出来。
知道了旋转角A之后，要把一个向量v:{x,y}逆时针旋转角度A，则结果向量v':{x',y'}为：

但是别忘了，还有缩放比例Scale。要把x’、y’分别乘以Scale。而Scale就是v2与v1的模之比，也就是：

可以把Scale直接乘到sin A和cos A里面去，正好约分掉一项，分母上的根号也没了。这样就变成了：

所以最终的转换公式为：

这样就完全没有浮点数运算，全部是整数。只要考查分子能不能除尽分母就可以知道结果是不是整数了。

2.如果星座是圆周对称图形的话，那么可能重复出现。比如星座是正方形，那么对于星相图中的同样4个点，你就会找到这个星作的4次出现。因此，在最终的结果中要除去重复的结果。
我的做法是，对于每一次出现，记录以下四颗星的坐标：x最小的星中y最小的、y最小的星是x最大的、x最大的星中y最大的、y最大的星中x最小的。也就是4个边界点。把它们存在一个数组里。靠它们就可以分辩出重复的出现并剃除了。

最后再提示一点原版题目中没有描述的信息：所有坐标的绝对值都不会超过50。

以下是我的AC代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>

using namespace std;

const int MAX_STAR = 1000;
const int MAX_STAR_PER_CONSTEL = 500;
const int NAME_LEN = 50;
const int COOR_BOUND = 100;
const int MAX_OCCUR = 500000;

struct Star {
    int x;
    int y;
    int bright;
};

//用来给一个星座里的star数组排序
int starCmp (const void* star1, const void* star2) {
    int result = ((Star*)star1)->x - ((Star*)star2)->x;
    if (result == 0) {
        result = ((Star*)star1)->y - ((Star*)star2)->y;
    }
    return result;
}

class Constel {
private:
    char m_name[NAME_LEN];
    Star m_star[MAX_STAR_PER_CONSTEL];
    int m_starCount;

public:
    void init() {
        m_starCount = 0;
    }

    void addStar(Star star) {
        m_star[m_starCount] = star;
        m_starCount++;
    }

    int bright() {
        int result = 0;
        for (int i = 0; i < m_starCount; i++) {
            result += m_star[i].bright;
        }
        return result;
    }

    void input() {
        scanf("%d %s", &m_starCount, m_name);
        for (int i = 0; i < m_starCount; i++) {
            scanf("%d %d", &m_star[i].x, &m_star[i].y);
        }
    }

    char* name() {
        return m_name;
    }

    void printConstel() {
        for (int i = 0; i < m_starCount; i++) {
            printf("(%d,%d)", m_star[i].x, m_star[i].y);
            if (i < m_starCount - 1) {
                printf(" ");
            }
            else {
                printf("\n");
            }
        }
    }

    Star star(int i) {
        return m_star[i];
    }

    int starCount() {
        return m_starCount;
    }

    void sortStar() {
        qsort(m_star, m_starCount, sizeof(Star), starCmp);
    }
};

//Map的成员，太大所以定义在外面
bool m_haveStar[COOR_BOUND * 2 + 1][COOR_BOUND * 2 + 1];
int m_starNo[COOR_BOUND * 2 + 1][COOR_BOUND * 2 + 1];

class Map {
private:
    Star m_star[MAX_STAR];
    int m_starCount;

    //把坐标转成m_haveStar中的下标
    inline int coorMap(int coor) {
        return coor + COOR_BOUND;
    }

public:
    bool input() {
        bool haveNext = false;
        scanf("%d", &m_starCount);
        if (m_starCount > 0) {
            haveNext = true;

            memset(m_haveStar, 0, sizeof(m_haveStar));

            for (int i = 0; i < m_starCount; i++) {
                scanf("%d %d %d", &m_star[i].x, &m_star[i].y, &m_star[i].bright);
                m_haveStar[coorMap(m_star[i].x)][coorMap(m_star[i].y)] = true;
                m_starNo[coorMap(m_star[i].x)][coorMap(m_star[i].y)] = i;
            }
        }
        return haveNext;
    }

    bool haveStar(int x, int y) {
        bool have;
        if (x > COOR_BOUND || x < -COOR_BOUND
            || y > COOR_BOUND || y < -COOR_BOUND
           ) {
            have = false;
        }
        else {
            have = m_haveStar[coorMap(x)][coorMap(y)];
        }
        return have;
    }

    Star star(int i) {
        return m_star[i];
    }

    Star star(int x, int y) {
        return m_star[m_starNo[coorMap(x)][coorMap(y)]];
    }

    int starCount() {
        return m_starCount;
    }
};

//星座在map中的一次出现。
//记录出现的左上角、左下角、右上角、右下角四个点。
struct Occur{
    Star leftLow;
    Star lowRight;
    Star rightHigh;
    Star highLeft;
};

//给Occur数组排序用。
int occurCmp(const void* occur1, const void* occur2) {
    Occur* p1 = (Occur*)occur1;
    Occur* p2 = (Occur*)occur2;
    int result = starCmp(&p1->leftLow, &p2->leftLow);
    if (result == 0) {
        result = starCmp(&p1->lowRight, &p2->lowRight);
    }
    if (result == 0) {
        result = starCmp(&p1->rightHigh, &p2->rightHigh);
    }
    if (result == 0) {
        result = starCmp(&p1->highLeft, &p2->highLeft);
    }
    return result;
}

//Solution的成员，太大了所以定义在外面
Occur m_occur[MAX_OCCUR];

class Solution {
private:
    Map m_map;
    int m_sketchCount;
    Constel m_sketch;
    int m_occurCount;
    Constel m_brightest;

    //对map中的一对星，考察如果它们对应星座中的前两颗星
    //，整个星座是否出现在map中。
    //返回一个Occur结构体。
    Constel checkOccur(Star occurStar1, Star occurStar2) {
        int sinUp;
        int cosUp;
        int down;
        getAngle(m_sketch.star(0), m_sketch.star(1), occurStar1, occurStar2
                 , sinUp, cosUp, down
                );

        Constel occurConstel;
        occurConstel.init();
        occurConstel.addStar(occurStar1);
        occurConstel.addStar(occurStar2);

        for (int i = 2; i < m_sketch.starCount(); i++) {
            Star oldStar = m_sketch.star(i);
            //把座星中的星[i]映射到map上，不经旋转和缩放。
            oldStar.x = occurStar1.x + (oldStar.x - m_sketch.star(0).x);
            oldStar.y = occurStar1.y + (oldStar.y - m_sketch.star(0).y);
            Star newStar = rotate(occurStar1, oldStar, sinUp, cosUp, down);
            if (m_map.haveStar(newStar.x, newStar.y)) {
                newStar.bright = m_map.star(newStar.x, newStar.y).bright;
                occurConstel.addStar(newStar);
            }
            else {
                occurConstel.init();
                break;
            }
        }

        return occurConstel;
    }

    //处理星座里只有一颗星的情况。
    void dealWithOneStar() {
        m_occurCount = m_map.starCount();

        Star brightest;
        brightest = m_map.star(0);
        for (int i = 1; i < m_occurCount; i++) {
            if (m_map.star(i).bright > brightest.bright) {
                brightest = m_map.star(i);
            }
        }
        m_brightest.init();
        m_brightest.addStar(brightest);
    }

    //跟据星座里的前两颗星和map中的某两颗星
    //，获得星座在map里的旋转角和缩放比例
    //，输出旋转角的sin和cos的分子、分母（两者的分母相等）。
    inline void getAngle(Star sketchStar1, Star sketchStar2
                         , Star occurStar1, Star occurStar2
                         , int& sinUp, int& cosUp, int& down
                        ) {
        int oldX = sketchStar2.x - sketchStar1.x;
        int oldY = sketchStar2.y - sketchStar1.y;
        int newX = occurStar2.x - occurStar1.x;
        int newY = occurStar2.y - occurStar1.y;
        sinUp = oldX * newY - newX * oldY;
        cosUp = oldX * newX + oldY * newY;
        down = oldX * oldX + oldY * oldY;
    }

    //把m_occur数组中重复的去掉（实际只是减少m_occurCount的值）
    void removeRepeat() {
        qsort(m_occur, m_occurCount, sizeof(Occur), occurCmp);

        int oldOccurCount = m_occurCount;
        int i = 0;
        while (i < oldOccurCount - 1) {
            int j = i + 1;
            while (j < oldOccurCount && occurCmp(&m_occur[i], &m_occur[j]) == 0) {
                //printf("%d %d\n", i, j);
                m_occurCount--;
                j++;
            }
            i = j;
        }
    }

    //把星old按center旋转（给出旋转角的sin和cos的分子、分母）。
    //如果结果坐标不是整数，则返回坐标为大于COOR_BOUND的值。
    inline Star rotate(Star center, Star old, int sinUp, int cosUp, int down) {
        Star result;
        int relativeX = old.x - center.x;
        int relativeY = old.y - center.y;
        int xUp = relativeX * cosUp - relativeY * sinUp;
        int yUp = relativeX * sinUp + relativeY * cosUp;
        if (xUp % down == 0 && yUp % down == 0) {
            result.x = center.x + xUp / down;
            result.y = center.y + yUp / down;
        }
        else {
            result.x = COOR_BOUND + 1;
            result.y = COOR_BOUND + 1;
        }
        return result;
    }

    //两颗星距离的平方
    inline int starDis(Star star1, Star star2) {
        return (star1.x - star2.x) * (star1.x - star2.x)
               + (star1.y - star2.y) * (star1.y - star2.y);
    }

    //找到一次occur的左下、左上、右下、右上四点
    void toOccur(Constel& constel, Occur& occur) {
        occur.leftLow = constel.star(0);
        occur.lowRight= constel.star(0);
        occur.rightHigh= constel.star(0);
        occur.highLeft = constel.star(0);
        for (int i = 1; i < constel.starCount(); i++) {
            Star current = constel.star(i);
            if(current.x < occur.leftLow.x
               || current.x == occur.leftLow.x && current.y < occur.leftLow.y
              ) {
                occur.leftLow = current;
            }
            if(current.y < occur.lowRight.y
               || current.y == occur.lowRight.y && current.x > occur.lowRight.x
              ) {
                occur.lowRight = current;
            }
            if(current.x > occur.rightHigh.x
               || current.x == occur.rightHigh.x && current.y > occur.rightHigh.y
              ) {
                occur.rightHigh = current;
            }
            if(current.y > occur.highLeft.y
               || current.y == occur.highLeft.y && current.x < occur.highLeft.x
              ) {
                occur.highLeft = current;
            }
        }
    }

public:
    bool input() {
        bool haveNext = m_map.input();
        if(haveNext) {
            scanf("%d", &m_sketchCount);
        }
        return haveNext;
    }

    bool inputConstel() {
        bool haveNext = false;
        if (m_sketchCount > 0) {
            haveNext = true;
            m_sketch.input();
            m_sketchCount--;
        }
        return haveNext;
    }

    void solve() {
        if (m_sketch.starCount() == 1) {
            dealWithOneStar();
        }
        else if (m_sketch.starCount() > m_map.starCount()) {
            m_occurCount = 0;
        }
        else {
            m_occurCount = 0;
            int maxBright = INT_MIN;

            for (int i = 0; i < m_map.starCount(); i++) {
                Star occurStar1 = m_map.star(i);
                for (int j = 0; j < m_map.starCount(); j++) {
                    if (j != i) {
                        Star occurStar2 = m_map.star(j);
                        Constel occurConstel = checkOccur(occurStar1, occurStar2);
                        //如果occurConstel中的星的数量为0，说明它没有出现。
                        if (occurConstel.starCount() > 0) {
                            occurConstel.sortStar();
                            int bright = occurConstel.bright();
                            if(bright > maxBright) {
                                maxBright = bright;
                                m_brightest = occurConstel;
                            }
                            //
                            toOccur(occurConstel, m_occur[m_occurCount]);
                            m_occurCount++;
                        }
                    }
                }
            }
            removeRepeat();
        }
    }

    void output() {
        printf("%s occurs %d time(s) in the map.\n", m_sketch.name(), m_occurCount);
        if (m_occurCount > 0) {
            printf("Brightest occurrence: ");
            m_brightest.printConstel();
        }
    }
};

int main() {
    Solution solution;
    int mapCount = 1;
    while (solution.input()) {
        printf("Map #%d\n", mapCount);
        while (solution.inputConstel()) {
            solution.solve();
            printf("\n");
            solution.output();
        }
        printf("-----\n");
        mapCount++;
    }
    return 0;
}