上海计算机学会2022年5月月赛C++乙组T2数山峰（二）
发布时间
阅读量：
阅读量
数山峰（二）
内存限制: 256 Mb时间限制: 1000 ms
题目描述
在平面直角坐标系上有 n 座像山峰一样的图案。每座山峰是一个直角等腰三角形，它们的底边都是坐标系的X轴，它们的峰顶在第一象限里，其中第 i 座山峰的峰顶坐标为 (xi,yi)。
给定每座山的峰顶坐标，请统计这些山覆盖的总面积是多少（重复覆盖部分只计算一次）。
输入格式
第一行：单个整数 nn；
第二行到第 n+1 行：第 i+1 行两个整数，表示一个峰顶的坐标 xi 与 yi。
输出格式
单个整数：设所有的山峰的可见面积为 s，因为希望输出整数，所以规定输出 4s。
数据范围
- 对于 30% 的数据，1≤n≤1,000；
- 对于 60% 的数据，1≤n≤10,000；
- 对于 100% 的数据，1≤n≤100,000；
- 1≤xi,yi≤100,000,000。
样例数据
输入:
3
1 1
2 1
4 1
输出:
11
说明:
前两个山峰有交集，面积为1+1+1-0.25=2.75
解析：
详见代码：
#include <bits/stdc++.h>
using namespace std;
struct st {
long long l;//左边山脚的X坐标
long long r;//右边山脚的X坐标
};
struct st a[100005];
//按左边山脚坐标排序，
//相同的右边山脚靠右的往前排
//保证不会落下左边覆盖右边
bool cmp(struct st s1, struct st s2) {
if (s1.l == s2.l) return s1.r >= s2.r;
else return s1.l < s2.l;
}
long long ans = 0;
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
long long x, y;
scanf("%d %d", &x, &y);
a[i].l = x - y;//计算左边山脚
a[i].r = x + y;//计算右边山脚
}
sort(a + 1, a + n + 1, cmp);//排序
long long mx = 0;
for (int i = 1; i <= n; i++) {
if (a[i].r > mx) { //没有完全被覆盖
ans += (a[i].r - a[i].l) * (a[i].r - a[i].l); //加上新山峰面积
if (a[i].l < mx) {
ans -= (mx - a[i].l) * (mx - a[i].l); //去掉重合部分
}
mx = a[i].r;
}
}
cout << ans << endl;
return 0;
}
全部评论 (0)
还没有任何评论哟~