程序设计天梯赛L3-9

题目 题意: 很长。大题意思是给定二维平面上n个点，按照x轴坐标从大到小的顺序给出。第一个点是你的老家，你要建立若干个烽火台，保证自己老家的安全。每个烽火台的视野有限，而且只能向x轴负方向看(和老家的方向相反)。Specially,与烽火台相切位置的点可以看到。求最少需要多少个烽火台。 思路: 根据样例瞎猜了一个峰顶，骗了18分，没啥思路。。。   看了带lao的思路，说若满足kab > kbc (相等恰好对应题目暗示的相切，独立思考能力实在有待提高。)，则被遮挡，需要在b处建烽火台，否则不需要，用单调栈维护。

时间复杂度: O(n) 代码:

#include
using namespace std;
const int N = 1e5+10;
typedef long long ll;
typedef pair PII;
PII va[N];
int st[N],top = 0; //单调栈
bool vis[N];
int n,m,k,T;
#define x first
#define y second
bool check(int a,int b,int c)
{
	return 1ll*(va[b].y-va[a].y)*(va[c].x-va[b].x) > 1ll*(va[c].y-va[b].y)*(va[b].x-va[a].x);
}
void solve()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=0;i>va[i].x>>va[i].y;
		while(top>=2 && !check(i,st[top-1],st[top-2])) top--;
		if(top>=1)
		vis[st[top-1]] = true;
		st[top++] = i; 
	}
	int ans = 0;
	for(int i=1;i