1. 距离之和
设 (x,y) 与 (x′,y′) 是平面上的两个点的坐标,它们之间的城市距离定义为
|x−x′|+|y−y′|
给定 n 个点,请计算任意两点的城市距离之和。
限制:
- 1⩽
- -10^6 \leqslant x_i, y_i \leqslant 10^6
算法分析
可以将 x 坐标和 y 坐标分开考虑
只讲 x 坐标的处理方法,y 坐标同理
先将所有点 x 的坐标排序,那么点 i 对前面 i-1 个点会贡献 x_i,对后面 n-i 个点会贡献 -x_i
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
ll f(vector<int> xs) {
int n = xs.size();
sort(xs.begin(), xs.end());
ll res = 0;
rep(i, n) {
ll co = +i-(n-i-1);
res += co*xs[i];
}
return res;
}
int main() {
int n;
cin >> n;
vector<int> x(n), y(n);
rep(i, n) cin >> x[i] >> y[i];
ll ans = f(x) + f(y);
cout << ans << '\n';
return 0;
}
2. ABC351E
考虑将切比雪夫坐标系转成曼哈顿坐标系,(x, y) \to (\frac{x+y}{2}, \frac{x-y}{2})
另外,原图上从点 (x_1, y_1) 能到达点 (x_2, y_2) 当且仅当这两个点的曼哈顿距离为偶数,那么旋转之后就变成了 x_1+y_1 和 x_2+y_2 的奇偶性要相同
然后就变成上面的题了
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
ll f(vector<int> xs) {
int n = xs.size();
sort(xs.begin(), xs.end());
ll res = 0;
rep(i, n) {
ll co = +i-(n-i-1);
res += co*xs[i];
}
return res/2;
}
int main() {
int n;
cin >> n;
vector<vector<int>> xs(2), ys(2);
rep(i, n) {
int X, Y;
cin >> X >> Y;
int x = X+Y;
int y = X-Y;
xs[x%2].push_back(x);
ys[x%2].push_back(y);
}
ll ans = 0;
rep(i, 2) ans += f(xs[i]) + f(ys[i]);
cout << ans << '\n';
return 0;
}
3. Max Manhattan Distance
给定平面上的 N 个点,P_1, P_2, \cdots, P_N,点 P_i 的坐标为 (x_i, y_i)
按顺序处理以下 Q 个询问:
- 给定整数 q_i,求出点 P_{q_i} 到平面上上其他点的曼哈顿距离的最大值
限制:
- 2 \leqslant N \leqslant 10^5
- 1 \leqslant Q \leqslant N
- -10^9 \leqslant x_i, y_i \leqslant 10^9
算法分析
考虑将曼哈顿坐标系转成切比雪夫坐标系 (x, y) \to (x+y, x-y)
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
inline void chmin(ll& x, ll y) { if (x > y) x = y; }
inline void chmax(ll& x, ll y) { if (x < y) x = y; }
int main() {
int n, q;
cin >> n >> q;
vector<ll> a(n), b(n);
const ll INF = 1e18;
ll min_a = INF, max_a = 0, min_b = INF, max_b = 0;
rep(i, n) {
ll x, y;
cin >> x >> y;
ll X = x+y;
ll Y = x-y;
a[i] = X;
b[i] = Y;
chmin(min_a, X);
chmax(max_a, X);
chmin(min_b, Y);
chmax(max_b, Y);
}
rep(qi, q) {
int i;
cin >> i;
--i;
ll ans = 0;
chmax(ans, abs(a[i]-min_a));
chmax(ans, abs(a[i]-max_a));
chmax(ans, abs(b[i]-min_b));
chmax(ans, abs(b[i]-max_b));
cout << ans << '\n';
}
return 0;
}
4. 多边形的面积
给出一个没有缺口的简单多边形,它的边是垂直或者水平的,要求计算多边形的面积。
多边形被放置在一个 xOy 的笛卡尔平面上,它所有的边都平行于两条坐标轴之一。然后按逆时针方向给出各顶点的坐标值。所有的坐标值都是整数,因此多边形的面积也为整数。
限制:
- 1 \leqslant n \leqslant 100
- -200 \leqslant x, y \leqslant 200
算法分析
对于每条边 \overrightarrow{AB},累加 \frac{\overrightarrow{OA} \times \overrightarrow{OB}}{2},最后得到的结果即为多边形的面积
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
struct Point {
int x, y;
Point(int x=0, int y=0): x(x), y(y) {}
int cross(const Point& o) const { return x*o.y - y*o.x; }
};
int main() {
int n;
cin >> n;
vector<Point> ps(n);
rep(i, n) cin >> ps[i].x >> ps[i].y;
int ans = 0;
rep(i, n) {
ans += ps[i].cross(ps[(i+1)%n]);
}
ans /= 2;
cout << ans << '\n';
return 0;
}