结果:\(\texttt{90 + 100 + 80 + 90 = 360 pts, rank 2}\)。
T1 HYH的线段
算法:计算几何(?)。
描述
HYH 第一类平面是一个无穷大的平面,另外 HYH 同学在平面上作出两条线段 \(AB\) 和 \(CD\)。
HYH 同学发现,两条线段可能相交,也可能不相交。HYH 同学觉得好神奇哦!所以他想要知道,两条线段的距离是多少。
线段 \(AB\) 和 \(CD\) 的距离定义为,线段 \(AB\) 上的点 \(P\) 和线段 \(CD\) 上的点 \(Q\)(均可与线段端点重合)的连线 \(PQ\) 长度的最小值。
现在给定两条线段的端点坐标,要求计算线段的距离。
输入
输入只有四行,每行两个整数(在 \([-100,100]\) 内),分别表示点 \(A,B,C,D\) 的坐标。
输出
输出只有一个四位小数,表示线段 \(AB\) 和 \(CD\) 的距离。
样例
共 \(1\) 组,不包含大样例。
样例 \(1\) 输入
0 5
0 4
-1 0
1 0
样例 \(1\) 输出
4.0000
题解
首先,对于线段相交的情况,直接输出 \(0.0000\) 即可。
反之,我们写一个函数,用于求出点到线段的最小距离。显然,这个距离要么是垂线(如果可以),要么与某个端点相连。
而不相交的情况下,我们只需要对于两条线段的四个端点分别计算到另一条线段的距离,然后四个距离取最小值即可。
但是垂线、平行等情况有可能出现除 \(0\) 导致 RE,所以要大力分讨一下。
#include<bits/stdc++.h>
#define y1 y_1
using namespace std;
inline double dis(double x1, double y1, double x2, double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
inline double dtoxd(double x1, double y1, double xax1, double xay1, double xbx1, double xby1){if(xax1 == xbx1){if(min(xay1, xby1) <= y1 && y1 <= max(xay1, xby1)){return fabs(xax1 - x1);}return min(dis(x1, y1, xax1, xay1), dis(x1, y1, xbx1, xby1));}else{double k = (xay1 - xby1) / (xax1 - xbx1);double b = xay1 - k * xax1;if(!k){if(min(xax1, xbx1) <= x1 && x1 <= max(xax1, xbx1)){return fabs(xay1 - y1);}return min(dis(x1, y1, xax1, xay1), dis(x1, y1, xbx1, xby1));}else{double czk = -1.0 / k;double czb = y1 - czk * x1;double x0 = (b-czb) / (czk-k);double y0 = k * x0 + b;if(min(xay1, xby1) <= y0 && y0 <= max(xay1, xby1)){return dis(x1, y1, x0, y0);}}}return min(dis(x1, y1, xax1, xay1), dis(x1, y1, xbx1, xby1));
}
double a1x, a1y, b1x, b1y, c1x, c1y, d1x, d1y;
inline double fab(double x){if(a1x == b1x) return 101;double k = (a1y - b1y) / (a1x - b1x);double b = a1y - k * a1x;return k * x + b;
}
inline double fcd(double x){if(c1x == d1x) return 101;double k = (c1y - d1y) / (c1x - d1x);double b = c1y - k * c1x;return k * x + b;
}
inline bool cross(){// cout << a1x << " " << b1x << endl;if(a1x == b1x){return min(a1y, b1y) <= fcd(a1x) && fcd(a1x) <= max(a1y, b1y);}// cout << "Here1";// cout<<fab(b1x) - fcd(b1x);exit(0);double cross1 = (fab(a1x) - fcd(a1x)) * (fab(b1x) - fcd(b1x));double cross2 = (fab(c1x) - fcd(c1x)) * (fab(d1x) - fcd(d1x));// cout << cross1 << " " << cross2 << endl;// if(!cross1 || ! cross2){// // cout << "duandian" << endl;// return true;// }return cross1 <= 0 && cross2 <= 0;
}
// inline void Print(){
// cout << a1x << " " << a1y << endl;
// cout << b1x << " " << b1y << endl;
// cout << c1x << " " << c1y << endl;
// cout << d1x << " " << d1y << endl;
// return;
// }
signed main(){// freopen("segment.in", "r", stdin);// freopen("segment.out", "w", stdout);cin >> a1x >> a1y;cin >> b1x >> b1y;cin >> c1x >> c1y;cin >> d1x >> d1y;// cout << "kkkkk";exit(0);if(a1x == b1x && c1x == d1x){if(min(a1y, b1y) <= c1y && c1y <= max(a1y, b1y)){cout << fixed << setprecision(4) << fabs(a1x-c1x) << '\n';}else if(min(a1y, b1y) <= d1y && d1y <= max(a1y, b1y)){cout << fixed << setprecision(4) << fabs(a1x-c1x) << '\n';}else{// Print();// cout << dis(1, 4, -1, 3) << endl;exit(0);double ans = min({dis(a1x, a1y, c1x, c1y) ,dis(a1x, a1y, d1x, d1y) ,dis(b1x, b1y, c1x, c1y) ,dis(b1x, b1y, d1x, d1y)});cout << fixed << setprecision(4) << ans << '\n';}return 0;}if(c1x == d1x){swap(a1x, c1x), swap(a1y, c1y);swap(b1x, d1x), swap(b1y, d1y);}if(cross()){cout << "0.0000" << '\n';return 0;}// Print();// cout << dtoxd(a1x, a1y, c1x, c1y, d1x, d1y) << endl;// cout << dtoxd(b1x, b1y, c1x, c1y, d1x, d1y) << endl;// cout << dtoxd(c1x, c1y, a1x, a1y, b1x, b1y) << endl;// cout << dtoxd(d1x, d1y, a1x, a1y, b1x, b1y) << endl;// cout << "jbjbjb";double ans = min({dtoxd(a1x, a1y, c1x, c1y, d1x, d1y) ,dtoxd(b1x, b1y, c1x, c1y, d1x, d1y) ,dtoxd(c1x, c1y, a1x, a1y, b1x, b1y) ,dtoxd(d1x, d1y, a1x, a1y, b1x, b1y)});cout << fixed << setprecision(4) << ans << '\n';return 0;
}