2421. Mountain View

2421. Mountain View

题目描述

从农场里奶牛Bessie的牧草地向远端眺望，可以看到巍峨壮丽的山脉绵延在地平线上。山脉里由N座山峰（1≤N≤10^5）。如果我们把Bessie的视野想象成xy平面，那么每座山峰都是一个底边在x轴上的三角形。山峰的两腰均与底边成45度角，所以山峰的峰顶是一个直角。于是山峰i可以由它的峰顶坐标(xi,yi)精确描述。没有两座山峰有完全相同的峰顶坐标。
Bessie尝试数清所有的山峰，然而由于它们几乎是相同的颜色，所以如果一座山峰的峰顶在另一座山峰的三角形区域的边界上或是内部，她就无法看清。
请求出Bessie能够看见的不同的山峰的峰顶的数量，也就是山峰的数量。

输入

输入的第一行包含N。以下N行每行包含xi（0≤xi≤10^{9）和yi（1≤yi≤10}9），描述一座山峰的峰顶的坐标。

输出

输出Bessie能够分辨出的山峰的数量。

样例输入

3
4 6
7 2
2 5

样例输出

2

提示

在这个例子中，Bessie能够看见第一座和最后一座山峰。第二座山峰被第一座山峰掩盖了。

思路：
首先来复习一下小学的数学知识，一个直角等腰三角形的高（过直角顶点的那条）=底(直角相对的那条底)/2。接着来做就简单了。
根据题意一座山如果不被挡住（拍照时，你的头不想被其他头挡住，你就别站比你高的人后面），那这座山一定是比较高，或者虽然矮，但没有在其他山的里面。于是思路就出来了。
我们先按照山的高矮做降序排序（从高到低）。一开始要假设所以山都能看见，再模拟每座山能挡住的山，将它们减掉。这样做会超时，最坏情况O（n^2）,但我们可以优化一下，只有没被挡住的山才能去挡更矮的山。数据比较水，God bless me！

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
using namespace std;
const int MAX=2147483647;
const int N=1e5+10;
struct node
{
	int d,h;
} s[N];
int n,ans;
bool vis[N];
bool cmp(node x,node y) {return x.h>y.h;}
void input()
{
	scanf("%d",&n);
	ans=n;
	for(int i=1;i<=n;i++) scanf("%d%d",&s[i].d,&s[i].h);
	sort(s+1,s+1+n,cmp);
}
int main()
{
	fre(mountains);
	input();
	for(int i=1;i<n;i++)
	{
		if(!vis[i]) //小小优化
		{
			int l=s[i].d-s[i].h,r=s[i].d+s[i].h;
			for(int j=i+1;j<=n;j++)
			{
				int ll=s[j].d-s[j].h,rr=s[j].d+s[j].h;
				if(l<=ll&&r>=rr&&!vis[j]) vis[j]=1,ans--;
			}	
		}
	}
	printf("%d\n",ans);
	return 0;
}

当然，大佬yty想到了O(n)的方法：

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
struct hhx{
	long long x,y;
}a[100010];
long long n,ans,x,y;
bool cmp(hhx t,hhx x)
{
	 if (t.x==x.x)
	    return (t.y>x.y);
	    else return (t.x<x.x);
}
int main()
{
	freopen("mountains.in","r",stdin);
	freopen("mountains.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
	    scanf("%d%d",&x,&y);
	    a[i].x=x-y;
	    a[i].y=x+y;
	}
	sort(a+1,a+n+1,cmp);
    x=0;
	for (int i=1;i<=n;i++)
	{ 
	    if (a[i].y>x)
	    {
	    	x=a[i].y;
	    	ans++;
		}
	}
	cout<<ans<<endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}