本题要求实现一个函数，对给定平面任意两点坐标(x \n1\n​\n ,y \n1\n​\n )和(x \n2\n​\n ,y \n2\n​\n )，求这两点之间的距离。

可以使用勾股定理求解，即距离等于两点横坐标差的平方加上纵坐标差的平方再开根号。具体公式为：

distance = sqrt((x2-x1)^2 + (y2-y1)^2)

其中，sqrt表示开根号的函数。

相关问题

本题要求实现一个函数，对给定平面任意两点坐标(x \n1\n​\t\n ,y \n1\n​\t\n )和(x \n2\n​\t\n ,y \n2\n​\t\n )，求这两点之间的距离。\n\n函数接口定义：\ndouble dist( d

ouble x1, double y1, double x2, double y2);\n\n其中，dist函数返回两点之间的距离，x1,y1,x2,y2分别为两点的横纵坐标。\n\n提示：两点之间的距离公式为：\n\ndistance = sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));\n\n其中，sqrt()函数为求平方根函数。

用C++解决以下问题：给定一小一大两个矩阵A,B，设计算法，在线性时间内找到在B中出现子块A，并输出出现的子块左上角的坐标(B最左上角坐标为 (0,0))。 第一行输入两个正整数n1,m1,分别表示小矩阵A行列数。n,m≤1300,n×m≤1.7×10 ^6。 接下来n1行每行输入m1个小写字母，表示A中的元素。 下一行输入两个正整数n2 ,m2，分别表示小矩阵B行列数。n≤3000,m≤20000,n⋅m≤4.5×10 ^7 接下来n2行每行输入m2个小写字母，表示B中的元素。 每一行输出B中出现的A的全部坐标。按行从小到大输出，行数相等的优先输出列数小的。给出相应的C++代码，要求时间复杂度为O(m),用中文回答问题

以下是C++代码实现：

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

// 定义哈希函数，将字符串转换为哈希值
int hashString(const string& str) {
    int hash = 0;
    for (int i = 0; i < str.length(); i++) {
        hash = hash * 31 + str[i];
    }
    return hash;
}

// 在大矩阵中查找子矩阵
void findSubMatrix(const vector<string>& small, const vector<string>& big) {
    int n = small.size(), m = small[0].length();
    int hash = hashString(small[0]);
    unordered_set<int> smallHashes;
    smallHashes.insert(hash); // 将第一行的哈希值加入哈希表中
    for (int i = 1; i < n; i++) {
        hash = hash * 31 + hashString(small[i]); // 计算整个子矩阵的哈希值
        smallHashes.insert(hash); // 将每一行的哈希值加入哈希表中
    }

    int bigHash = 0;
    for (int i = 0; i < n; i++) {
        bigHash = bigHash * 31 + hashString(big[i].substr(0, m)); // 计算第一行的哈希值
    }
    if (smallHashes.count(bigHash)) { // 如果第一行的哈希值在哈希表中，则输出当前坐标
        cout << 0 << " " << 0 << endl;
    }

    // 计算每一列的哈希值，并在哈希表中查找与之匹配的子矩阵哈希值
    int base = 1;
    for (int j = 1; j < m; j++) {
        bigHash = 0;
        for (int i = 0; i < n; i++) {
            bigHash = bigHash * 31 + hashString(big[i].substr(j, m-j)); // 计算当前列的哈希值
        }
        base = base * 31; // 更新base值，用于计算下一列的哈希值
        if (smallHashes.count(bigHash)) { // 如果当前列的哈希值在哈希表中，则输出当前坐标
            cout << 0 << " " << j << endl;
        }
    }

    // 在剩余的行中查找子矩阵
    for (int i = n; i < big.size(); i++) {
        bigHash = 0;
        for (int j = 0; j < n; j++) {
            bigHash = bigHash * 31 + hashString(big[i-n].substr(j, m-j)); // 计算上一次匹配的哈希值
        }
        bigHash -= base * hashString(big[i-n]); // 减去上一次匹配的第一行的哈希值
        bigHash = bigHash * 31 + hashString(big[i].substr(0, m)); // 加上当前行的哈希值
        if (smallHashes.count(bigHash)) { // 如果当前行匹配成功，则输出当前坐标
            cout << i-n+1 << " " << 0 << endl;
        }
        for (int j = 1; j < m; j++) {
            bigHash -= base * hashString(big[i-n].substr(j-1, m-j+1)); // 减去上一列的哈希值
            bigHash = bigHash * 31 + hashString(big[i].substr(j, m-j)); // 加上当前列的哈希值
            if (smallHashes.count(bigHash)) { // 如果当前列匹配成功，则输出当前坐标
                cout << i-n+1 << " " << j << endl;
            }
        }
    }
}

int main() {
    int n1, m1, n2, m2;
    cin >> n1 >> m1;
    vector<string> small(n1);
    for (int i = 0; i < n1; i++) {
        cin >> small[i];
    }
    cin >> n2 >> m2;
    vector<string> big(n2);
    for (int i = 0; i < n2; i++) {
        cin >> big[i];
    }

    findSubMatrix(small, big);

    return 0;
}

该算法的时间复杂度为O(m)，其中m为大矩阵的元素个数。算法的基本思路是先计算子矩阵的哈希值，然后在大矩阵中计算每个子矩阵的哈希值进行匹配。为了优化计算时间，我们使用了滚动哈希的方法，避免了重复计算哈希值。