英文题干

This problem is a variant of the General’s Horse Drinking Water problem.

Given that the general’s horse is at point , the tent is at point , and the river is located along the positive half of the x-axis and the positive half of the y-axis, find the shortest distance the horse needs to travel to drink water from the river and return to the tent.

Input:

Each test contains multiple test cases. The first line contains the number of test cases . The description of the test cases follows.

Each test case consists of a single line containing four integers , describing the positions of the general’s horse and the tent.

Output:

For each test case, output a decimal number representing the shortest distance the horse needs to travel to drink water from the river and return to the tent.

Your answer is considered correct if its absolute or relative error does not exceed .

Formally, let your answer be , and the jury’s answer be . Your answer is accepted if and only if .

中文题干

这个问题是将军饮马问题的一个变种。

假设将军的马位于点，帐篷位于点，河流沿着x轴正半轴和y轴正半轴，找出马需要行进的最短距离，喝水后返回帐篷。

思路

简单的初中几何签到题

  1. 因为有横竖两个岸，我们只需要求马分别到两个岸喝水所需的最短长度（对称+勾股），然后求较小值即可（注意开long long以及小数位数的保留）。

AC代码

时间复杂度：O()

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int infmin = 0xc0c0c0c0;
const int infmax = 0x3f3f3f3f;
const int maxn = 5e5 + 10;



signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        int A1 = abs(x2 - x1);
        int B1 = abs(y2 + y1);
        int TG1 = A1 * A1 + B1 * B1;
        double X = sqrt((double)TG1);

        int A2 = abs(x2 + x1);
        int B2 = abs(y2 - y1);
        int TG2 = A2 * A2 + B2 * B2;
        double Y = sqrt((double)TG2);

        double Z = min(X, Y);
        
        int test = Z;
        if(test*test==min(TG1,TG2)){
            cout << Z << "\n";
            continue;
        }

        cout.precision(14);
        cout << fixed << Z << "\n";
    }

    return 0;
}