撰写1 second
256 megabytes
standard input
standard output
In this problem we consider a very simplified model of Barcelona city.
Barcelona can be represented as a plane with streets of kind x=cx=c and y=cy=c for every integer cc (that is, the rectangular grid). However, there is a detail which makes Barcelona different from Manhattan. There is an avenue called Avinguda Diagonal which can be represented as a the set of points (x,y)(x,y) for which ax+by+c=0ax+by+c=0.
One can walk along streets, including the avenue. You are given two integer points AA and BB somewhere in Barcelona. Find the minimal possible distance one needs to travel to get to BB from AA.
The first line contains three integers aa, bb and cc (−109≤a,b,c≤109−109≤a,b,c≤109, at least one of aa and bb is not zero) representing the Diagonal Avenue.
The next line contains four integers x1x1, y1y1, x2x2 and y2y2 (−109≤x1,y1,x2,y2≤109−109≤x1,y1,x2,y2≤109) denoting the points A=(x1,y1)A=(x1,y1) and B=(x2,y2)B=(x2,y2).
Find the minimum possible travel distance between AA and BB. Your answer is considered correct if its absolute or relative error does not exceed 10−610−6.
Formally, let your answer be aa, and the jury’s answer be bb. Your answer is accepted if and only if |a−b|max(1,|b|)≤10−6|a−b|max(1,|b|)≤10−6.
1 1 -3 0 3 3 0
4.2426406871
3 1 -9 0 3 3 -1
6.1622776602
The first example is shown on the left picture while the second example us shown on the right picture below. The avenue is shown with blue, the origin is shown with the black dot.
题意：给出两点一线（一般式）一grid，要求只能在线与grid之间走，求A，B间最短距离。
题解：分类后可知工五种情况，一种为曼哈顿距离，其余为在线上的与点A连线与grid平行两点、在线上的与点B连线与grid平行两点之间的组合。（四种d1+d2+dis（A，B））
代码:
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
const int maxn=1e5+10;
double dis(double x_1,double y_1,double x_2,double y_2)
{
return sqrt((x_1-x_2)*(x_1-x_2)+(y_1-y_2)*(y_1-y_2));
}
double Manhattan(double x_1,double y_1,double x_2,double y_2){
return fabs(x_1-x_2)+fabs(y_1-y_2);
}
double a,b,c,x_1,x_2,y_1,y_2;
int main(){
ios::sync_with_stdio( false );
cin>>a>>b>>c;
c=-c;
cin>>x_1>>y_1>>x_2>>y_2;
double ans=Manhattan(x_1,y_1,x_2,y_2);
double ay_1=y_1;
double ax_1=(c-b*ay_1)/a;
double ad1=fabs(ax_1-x_1);
double ax_2=x_1;
double ay_2=(c-a*ax_2)/b;
double ad2=fabs(ay_2-y_1);
double by_1=y_2;
double bx_1=(c-b*by_1)/a;
double bd1=fabs(bx_1-x_2);
double bx_2=x_2;
double by_2=(c-a*bx_2)/b;
double bd2=fabs(by_2-y_2);
double d=dis(ax_1,ay_1,bx_1,by_1)+ad1+bd1;
ans=min(ans,d);
d=dis(ax_1,ay_1,bx_2,by_2)+ad1+bd2;
ans=min(ans,d);
d=dis(ax_2,ay_2,bx_1,by_1)+ad2+bd1;
ans=min(ans,d);
d=dis(ax_2,ay_2,bx_2,by_2)+ad2+bd2;
ans=min(ans,d);
cout << fixed << setprecision(10) << ans << endl;
return 0;
}