\(\text{By hhoppitree.}\)
\(\textbf{Round 1 A. }\) Apair
题目大意
给定平面直角坐标系上的 \(n\) 个整点，求任意两个不同的点的曼哈顿距离与欧几里得距离的比的最大值，多组询问。
数据范围：\(T\le10,n\le10^5\)，\(\texttt{1s/512MB}\)。
思路分析
考虑我们就是要让连线段的角度最接近 \(\dfrac{\pi}{4}\) 或 \(\dfrac{3\pi}{4}\)，将平面直角坐标系旋转对应角度后也就是要求连线段与 \(x\) 轴夹角最小的两个点。
按旋转后的 \(y\) 坐标排序后，最优解一定可以在两个点相邻的时候取到，证明可以画画图。
最终的时间复杂度为单组询问 \(\mathcal{O}(n\log n)\)。
代码呈现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const long double pi = acos(-1.0);
int n;
pair<int, int> c[N];
int cmp1(pair<int, int> x, pair<int, int> y) {
return x.first + x.second < y.first + y.second;
}
int cmp2(pair<int, int> x, pair<int, int> y) {
return x.first - x.second < y.first - y.second;
}
long double calc() {
long double res = 0;
for (int i = 1; i < n; ++i) {
int x = abs(c[i].first - c[i + 1].first), y = abs(c[i].second - c[i + 1].second);
res = max(res, (x + y) / hypot((long double)x, (long double)y));
}
return res;
}
signed main() {
freopen("Apair.in", "r", stdin);
freopen("Apair.out", "w", stdout);
int T; scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d%d", &c[i].first, &c[i].second);
sort(c + 1, c + n + 1, cmp1);
long double res = calc();
sort(c + 1, c + n + 1, cmp2);
printf("%.20Lf\n", max(res, calc()));
}
return 0;
}