NC24198. [USACO 2019 Jan S]Mountain View
描述
Bessie尝试数清所有的山峰，然而由于它们几乎是相同的颜色，所以如果一座山峰的峰顶在另一座山峰的三角形区域的边界上或是内部，她就无法看清。
请求出Bessie能够看见的不同的山峰的峰顶的数量，也就是山峰的数量。
输入描述
输入的第一行包含N。以下N行每行包含xi（0≤xi≤10^9）和yi（1≤yi≤10^9），描述一座山峰的峰顶的坐标。
输出描述
输出Bessie能够分辨出的山峰的数量。
示例1
输入:
3 4 6 7 2 2 5
输出:
2
说明:
在这个例子中，Bessie能够看见第一座和最后一座山峰。第二座山峰被第一座山峰掩盖了。C++14(g++5.4) 解法, 执行用时: 87ms, 内存消耗: 1080K, 提交时间: 2020-09-07 20:10:45
#include<bits/stdc++.h>
using namespace std;
struct node{
int l,r;
}m[100100];
int n,w,s,x,y;
int cmp(node a,node b){return a.l<b.l||(a.l==b.l&&a.r>b.r);}//排序方法
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>x>>y,m[i].l=x-y,m[i].r=x+y;//算出左右端点
sort(m+1,m+n+1,cmp);
for(int i=1;i<=n;i++)if(m[i].r>w)s++,w=m[i].r;//如果大于当前所有山的右端点，答案+1，更新最大右端点
cout<<s;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 145ms, 内存消耗: 2016K, 提交时间: 2020-09-06 15:58:11
#include<cstdio>
long long x[100003],y[100003],tot,n;
int main() {
scanf("%d",&n);tot=n;
for(int i=1;i<=n;i++) scanf("%lld%lld",&x[i],&y[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)if(i!=j)
if(y[j]+x[j]>=y[i]+x[i]&&x[j]-y[j]<=x[i]-y[i]){tot--;break;}
printf("%d",tot);
return 0;
}