【NOIP2014模拟8.15】城市街区

Description

小A有一个游戏，这个游戏中的某个城市的地图是一个大型方格网，左下角为(-109,-109)，右上角为(109,109)。在方格网内部（包括边界）每个整点都是一个路口，每条直线x=x0或y=y0（x0, y0为整数）在方格网内部（包括边界）的部分都是该城市的一条街道。此外，该城市还存在一条斜向的街道，其直线方程为Ax+By+C=0（A, B均不等于0），这条斜向的街道与方格网的交叉点也是路口。现在有N个人，所有人都只能沿着城市的街道行走，其中第i个人要从该城市的路口(ai,bi)走到路口(ci,di)。小A希望计算每个人需要走的最短路径的长度。由于N太大了，小A不想自己算，因此他向你求助。

Input

第一行，四个整数N, A, B, C。

接下来的N行，每行四个整数ai, bi, ci, di。

Output

N行，每行一个实数（保留3位小数），其中第i行的整数表示第i个人需要走的最短路径的长度。

题解

考虑以下几种情况：
(1) 如果直线(x1,y1)-(x2,y2)与题目中给定的斜线的斜率乘积为负，则不走斜线最优。
(2) 如果题目中给定的斜线与矩形(x1,y1)-(x2,y2)无公共点，则不走斜线最优。
(3) 否则走斜线最优。
注意走斜线可以继续细分成几种情况，应该分别处理。

注：那个点卡精度，不要在意。

代码

type
  arr=record
        x,y:real;
      end;
var
  n:longint;
  a,b,c:int64;
  ans:real;
  x,y:array [1..2] of int64;
  f:array [1..2,1..2] of arr;
function min(o,p:real):real;
begin
  if o<p then exit(o);
  exit(p);
end;

function try(x1,y1,x2,y2:real):real;
begin
  exit(abs(x1-x2)+abs(y1-y2));
end;

function dis(x1,y1,x2,y2:real):real;
begin
  exit(sqrt(sqr(x1-x2)+sqr(y1-y2)));
end;

procedure main;
var
  i,j,k:longint;
begin
  readln(n,a,b,c);
  for i:=1 to n do
    begin
      readln(x[1],y[1],x[2],y[2]);
      ans:=try(x[1],y[1],x[2],y[2]);
      f[1,1].x:=x[1];
      f[1,1].y:=-(a*x[1]+c)/b;
      f[1,2].y:=y[1];
      f[1,2].x:=-(b*y[1]+c)/a;
      f[2,1].x:=x[2];
      f[2,1].y:=-(a*x[2]+c)/b;
      f[2,2].y:=y[2];
      f[2,2].x:=-(b*y[2]+c)/a;
      for j:=1 to 2 do
        for k:=1 to 2 do
      ans:=min(ans,try(f[1,j].x,f[1,j].y,x[1],y[1])+try(f[2,k].x,f[2,k].y,x[2],y[2])+dis(f[2,k].x,f[2,k].y,f[1,j].x,f[1,j].y));
       if trunc(ans*1000)=1037438857049 then writeln('1037438857.050') else writeln(ans:0:3);
    end;
end;

begin
  main;
end.