几何+lis
很巧妙。直接做很困难，那么我们转化一下，把每个点能看见的圆弧画出来。只有这些圆弧相交时才满足条件。
那么也就是找出圆上尽量多两两相交的区间。
所以我们先按左端点极角排序，然后固定一个必须选的区间，找出所有和它相交的区间，按右端点做lis就行了。
#include<bits/stdc++.h> using namespace std; const int N = 2010; const double pi = acos(-1); struct data { double l, r; int id; } x[N], a[N]; int n, ans; double R; int tree[N << 2], dp[N]; void update(int l, int r, int x, int pos, int t) { if(l == r) { tree[x] = t; return; } int mid = (l + r) >> 1; if(pos <= mid) update(l, mid, x << 1, pos, t); else update(mid + 1, r, x << 1 | 1, pos, t); tree[x] = max(tree[x << 1], tree[x << 1 | 1]); } int query(int l, int r, int x, int a, int b) { if(l > b || r < a) return 0; if(l >= a && r <= b) return tree[x]; int mid = (l + r) >> 1; return max(query(l, mid, x << 1, a, b), query(mid + 1, r, x << 1 | 1, a, b)); } int lis(int t) { if(!t) return 0; int ans = 1; dp[1] = 1; memset(tree, 0, sizeof(tree)); update(1, n, 1, x[1].id, dp[1]); for(int i = 2; i <= t; ++i) { dp[i] = query(1, n, 1, 1, x[i].id) + 1; ans = max(ans, dp[i]); update(1, n, 1, x[i].id, dp[i]); } return ans; } bool cp1(data x, data y) { return x.r < y.r; } bool cp(data x, data y) { return x.l < y.l; } int main() { scanf("%d%lf", &n, &R); for(int i = 1; i <= n; ++i) { double x, y; scanf("%lf%lf", &x, &y); double degx = atan2(y, x); double degc = acos(R / sqrt(x * x + y * y)); a[i].l = degx - degc; a[i].r = degx + degc; while(a[i].l <= -pi) a[i].l += 2 * pi; while(a[i].r >= pi) a[i].r -= 2 * pi; if(a[i].l > a[i].r) swap(a[i].l, a[i].r); } sort(a + 1, a + n + 1, cp1); for(int i = 1; i <= n; ++i) a[i].id = i; sort(a + 1, a + n + 1, cp); for(int i = 1; i <= n; ++i) { int t = 0; for(int j = i + 1; j <= n; ++j) if(a[j].l <= a[i].r && a[j].r >= a[i].r) x[++t] = a[j]; ans = max(ans, lis(t) + 1); } printf("%d ", ans); return 0; }