计算几何基础

判断两点是否在同一对角线上

给定两个点 A(x1,y1) 和 B(x2,y2) B(x2,y2)

若 abs(x1 - x2) == abs(y1 - y2)，两点同一条对角线（/）上。

若x1 - y1 == x2 - y2，两点在主对角线  上。

若x1 + y1 == x2 + y2，两点在次对角线 / 上。

1128 N Queens Puzzle - PAT (Advanced Level) Practice (pintia.cn)

以N皇后问题为例：

O(n2)写法，较为简便，但效率低

bool solve(){
    for(int i = 1; i <= n; i++){ //这里i表示行，col[i]表示列
        for(int j = i + 1; j <= n; j++){
            if(col[i] == col[j] || abs(i - j) == abs(col[i] - col[j])){
                return false;
            }
        }
    }
    return true;
}

O(n)写法，哈希优化，较为繁琐，但效率高

bool solve(){
    //这里i表示行，col[i]表示列
    memset(vis, false, sizeof(vis));
    for(int i = 1; i <= n; i++){ //列
        if(vis[col[i]]) return false;
        vis[col[i]] = true;
    }
    memset(vis, false, sizeof(vis));
    for(int i = 1; i <= n; i++){ //主对角线
        int tep = i - col[i] + 1500;
        if(vis[tep]) return false;
        vis[tep] = true;
    }
    memset(vis, false, sizeof(vis));
    for(int i = 1; i <= n; i++){ //次对角线
        int tep = i + col[i];
        if(vis[tep]) return false;
        vis[tep] = true;
    }
    return true;
}