不会推结论，单调队列万岁！
题目大意: 给出若干个等腰直角三角形的顶点，要求有多少个点没有被其他三角形覆盖
先按$x$坐标对顶点排序，单调队列维护所有未被覆盖的点，对于$i$，把它可以覆盖的点从队尾弹出(即队尾元素的左端点≥i的左端点)，执行完操作后，如果$i$未被现在的队尾覆盖就入队。
最后队内元素个数就是答案
#include<iostream> #include<iomanip> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<deque> using namespace std; inline int read() { char ch; int bj=1; while(!isdigit(ch=getchar())) bj=(ch=='-')?-1:1; int res=ch^(3<<4); while(isdigit(ch=getchar())) res=(res<<1)+(res<<3)+(ch^(3<<4)); return res*bj; } void printnum(int x) { if(x>9)printnum(x/10); putchar(x%10+'0'); } inline void print(int x,char ch) { if(x<0) { putchar('-'); x=-x; } printnum(x); putchar(ch); } int n,ans; struct node { int x,y; inline bool operator < (node a)const { return x<a.x; } } a[100005]; deque<int>q; int main() { n=read(); for(int i=1; i<=n; i++) { a[i].x=read(); a[i].y=read(); } sort(a+1,a+n+1); for(int i=1; i<=n; i++) { while(!q.empty()&&a[q.back()].x-a[q.back()].y>=a[i].x-a[i].y)q.pop_back(); if(!q.empty()&&a[q.back()].x-a[q.back()].y<=a[i].x-a[i].y&&a[q.back()].x+a[q.back()].y>=a[i].x+a[i].y)continue; q.push_back(i); } print(q.size(),'\n'); return 0; }