Barcelonian Distance

Created by LXC on Fri Feb 23 00:24:48 2024

https://codeforces.com/problemset/problem/1032/D

ranting: 1900

tag: geometry, implementation

problem

题目描述

给出一个在二维平面直角坐标系第一象限内的，单位长度为1的无限大网格，每条直线都代表道路。又给你一条直线ax+by+c=0，也代表一条道路。
现在给你两个格点A,B坐标(x1,y1)和(x2,y2)，让你求该两点间最短的道路距离。

输入

第一行a,b,c表示直线ax+by+c=0
第二行x1,y1,x2,y2表示A(x1,y1),B(x2,y2)的坐标

输出

求A,B间最短的道路距离（误差不超过10^−6）

solution

$(x1,y1)$ 到 $(x2, y2)$ 的移动方式，在经过直线是可以沿着直线走，否则只能水平或竖直移动。

分两种情况

不经过直线$ax+by+c=0$，那么他们的距离是曼哈顿距离$|x1-x2|+|y1-y2|$

经过直线$ax+by+c=0$，由于点$(x,y)$存在两种方式到达直线，交点分别是$(x, (-c-ax)/b),((-c-by)/a, x)$。存在4种不同移动方案，只需维护4种方案的最小值就是经过直线情况的最小值。

两种情况的最小值就是答案。

吐槽一下x1, x2, y1, y2作为全局变量似乎与c++自带的库冲突了

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

// ax + by + c = 0
ll a, b, c;
ll X1, Y1, X2, Y2;

// (x, y')  y' = (-c-ax)/b
pair<double, double> getp1(double x, double y) {
    return {x, (-c-a*x)/b};    
}

// (x', y)  x' = (-c-by)/a
pair<double, double> getp2(double x, double y) {
    return {(-c-b*y)/a, y};    
}

double dis(double a1, double b1, double a2, double b2) {
    return sqrt((a1-a2)*(a1-a2)+(b1-b2)*(b1-b2));
}

void sol() {
    cin >> a >> b >> c;
    cin >> X1 >> Y1 >> X2 >> Y2;
    vector<pair<double, double>> v1;
    v1.push_back(getp1(X1, Y1));
    v1.push_back(getp2(X1, Y1));
    vector<pair<double, double>> v2;
    v2.push_back(getp1(X2, Y2));
    v2.push_back(getp2(X2, Y2));
    // cout << v1 << " " << v2 << endl;
    double ans = abs(X1-X2)+abs(Y1-Y2);
    for (auto [a1, b1]:v1) {
        for (auto [a2, b2]:v2) {
            ans = min(ans, dis(X1, Y1, a1, b1)+dis(a1, b1, a2, b2)+dis(a2, b2, X2, Y2));
        }
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}