题解 P5199【 [USACO19JAN]Mountain View】
Rbu_nas
2019-03-05 22:38:18
本题理解题意就很好写了,模拟思路很好想。
注意一下「山」是沿$x$轴正方向蔓延的,并不是排成一列然后站在队首观望山峰的,也就是说我们预处理一下等腰直角三角形的左端点和右端点,不要被大的山所覆盖就好了。然后由于是等腰直角三角形,计算端点也没啥好说的
![](https://cdn.luogu.com.cn/upload/pic/53256.png)
剩下的就是模拟了,加了快读跑到了rk1:
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
#define gcc getchar
template <typename T> inline void read(T&x)
{
x=0; bool f=true; char ck=gcc();
for( ; ck<'0'||ck>'9'; ck=gcc()) if(ck == '-') f=false;
for( ; ck>='0'&&ck<='9'; ck=gcc()) x=(x<<1)+(x<<3)+(ck^48);
x=f?x:-x; return ;
}
#define N 100003
int n, maxr, res;
struct Node
{
int l, r;
bool operator < (const Node&other) const
{
return (l != other.l) ? (l < other.l) : (r > other.r);
}
//按左端点作为关键字排序,如果一样那么只能看到大的山了
} ;
Node a[N];
int main(void)
{
read(n);
for(int i=1; i<=n; ++i)
{
int x, y; read(x), read(y);
a[i].l=x-y, a[i].r=x+y;
//简单的预处理,如果不是等腰直角三角形也一样作垂线用三角函数
}
sort(a+1, a+n+1);
for(int i=1; i<=n; ++i)
if(a[i].r > maxr) ++res, maxr=a[i].r;
//每一次更新最右端点,不超过maxr的则会被大山包含
printf("%d", res);
return 0;
}
```