题解 【方分】

## 题目大意 平面直角坐标系中，有两个不相交的正方形。求任意一条在这两个正方形之间的直线解析式。直线不能与正方形有交点。 这里是$\stackrel{\text{咕咕咕}}{\text{迟到}}$的官方题解。 ## 题解 我们只需要枚举 $8$ 条边，将其进行微调（向上移或者向下移，具体移动多少要看精度，只要 $\text{SPJ}$ 不会判相交就行），判断是否可行即可。下证这种做法的正确性。 考虑到我们只关心两个正方形的相对位置，因此我们可以把其中一个正方形固定到坐标原点，并使其边与坐标轴平行。另一个正方形可以放到它的右上角（或者说，可以通过左右翻转、上下翻转操作使得这个正方形总是处在第一个正方形的上方、右方部分）。 - 当正方形 $CDHG$ 没有点在 $EF$ 下时，显然所求直线在 $EF$ 上方平移一点点。  - 当正方形 $CDHG$ 没有点在 $BE$ 右时，显然所求直线在 $BE$ 右方平移一点点。  - 当正方形 $CDHG$ 同时有点在 $EF$ 下方、$BE$ 右方时，取这两个点的连线即可。在下图中，所求直线即为 $GH$ 下方平移一点点。  关于点在直线位置的判定，假设有一个直线的解析式为 $Ax+By+C=0$ ，那么带入点的坐标 $(x_0,y_0)$ ，所得的 $Ax_0+By_0+C$ 的正负即可作为判定该点在直线位置的标准。特别地，如果 $Ax_0+By_0+C=0$ ，那么就说明这个点在直线上。不过通过微调，我们总是能保证不会有正方形顶点在所求直线上。 另外，作为出题人，这里有必要谈一点细节： - 虽然 $\text{SPJ}$ 使用双精度浮点数，但由于误差是会被平方放大的，请务必保证你的结果精度足够高（位数多一点好）。 - 因为是多测，所以大概卡掉了一些奇怪的做法。数据出的可能有些毒瘤（） - 这题难点可能在于不容易想到构造方法。但一旦想到了，其实是比较容易构造的。 ## 参考代码 ```cpp #include<bits/stdc++.h> #define up(l,r,i) for(int i=l;i<=r;i++) #define dn(l,r,i) for(int i=l;i>=r;i--) using namespace std; typedef double f64; const f64 eps=1e-8; bool f; f64 A[5][2],B[5][2]; int T; bool clc(f64 x,f64 y,f64 a,f64 b,f64 c){return a*x+b*y+c>0;} bool fnd(f64 a,f64 b,f64 c){ if(f) return false; bool t=clc(A[1][0],A[1][1],a,b,c); up(1,4,i) if(clc(A[i][0],A[i][1],a,b,c)!=t) return false; up(1,4,i) if(clc(B[i][0],B[i][1],a,b,c)==t) return false; printf("%.12lf %.12lf %.12lf\n",a,b,-c); return f=true; } bool chk(f64 x0,f64 y0,f64 x1,f64 y1){ if(f) return false; f64 a=y1-y0,b=x0-x1,c=y0*(x1-x0)-x0*(y1-y0); return fnd(a,b,c+eps)|fnd(a,b,c-eps); } int main(){ scanf("%d",&T); dn(T,1,TEST){ f=false; up(1,4,i) scanf("%lf%lf",&A[i][0],&A[i][1]); up(1,4,i) scanf("%lf%lf",&B[i][0],&B[i][1]); up(1,4,i) up(1,i-1,j) if(!f){ chk(A[i][0],A[i][1],A[j][0],A[j][1]), chk(B[i][0],B[i][1],B[j][0],B[j][1]); } } return 0; } /* x+y+0.005=0 y=-0.005 */ ```