一开始一直在想这题，首先烽火站点肯定放在凸点，凹点肯定没后面的凸点更优。
那么主要就在于判断是否这个凸点没有放置的必要。
于是就有一个N^2的做法，去暴力判断。
然后我就开始考虑优化，但是没怎么想出来。
其实并没有那么难。
类似单调栈的思想去维护一个有设立烽火站的凸点的栈。
对于三个点，a,b,c。b为中点。
如果ab的斜率 > bc的斜率，那么这个b的凸点就必须要去放了，不然就会导致c无法看见a。
这样去维护栈即可。
这里肯定有一个疑问，如果c的后面的点可以取带c点来看见a，那么会不会少了这种方案。
答案是不会，因为我们栈中维护的都是有设立的点，如果那个后面的点可以看见a，那么说明那个点也可以看见c。
那么c就不会设立，这样就可以明白，存在栈中的点去看前面很正确。
然后注意，一个点可能会多次去被判断，这样不能重复设立，我们对每个点做一个标记来表示有没有设立，最后统计即可。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 2e3 + 5; const LL Mod = 2147483647; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; LL x[N],y[N]; /* double k1 = (y[k] - y[j]) / (x[k] - x[j]); double k2 = (y[j] - y[i]) / (x[j] - x[i]); 能看见 k2 <= k1 (y[k] - y[i]) * (x[k] - x[j]) <= (y[k] - y[j]) * (x[j] - x[i]); */ bool check(int i,int j,int k) {//i - now,j - middle,k - right return (y[j] - y[i]) * (x[k] - x[j]) <= (y[k] - y[j]) * (x[j] - x[i]); } int S[N],vis[N]; int main() { int n;n = read(); int top = 0; for(int i = 1;i <= n;++i) { x[i] = read(),y[i] = read(); while(top >= 2 && check(i,S[top],S[top - 1])) top--; vis[S[top]] = 1; S[++top] = i; } int ans = 0; for(int i = 2;i <= n;++i) if(vis[i]) ans++; printf("%d ",ans); system("pause"); return 0; }