题意:有一堆兔子，还有一个r为半径的圆，要求找到最大集合满足这个集合里的兔子两两连边的直线不经过圆。
思路:发现如果有两个点之间连边不经过圆，那么他们到圆的切线会构成一段区间，那么这两个点的区间一定会有交集，形如s0 s1 e0 e1
同样的，如果是n个点，那就是s0 s1 s2..sn e0 e1 e2.. en
因此，我们枚举那个起始点，然后对于其他点我们按照s排序，对于e做最长上升子序列即可。时间复杂度O（n^2 logn)
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
const double pi = 3.14159265358979324;
double th1[], th2[], b[], x[], y[];
std::pair<std::pair<double, double>, int> a[];
int t[], t2[], f[], n;
std::vector<int> ansv;
double r;
int main() {
freopen("crazy.in", "r", stdin);
freopen("crazy.out", "w", stdout);
scanf("%d%lf", &n, &r);
for (int i = ; i < n; i++) {
scanf("%lf%lf", &x[i], &y[i]);
double th = atan2(y[i], x[i]);
double dth = acos(r / sqrt(x[i] * x[i] + y[i] * y[i]));
th1[i] = th + dth; if (th1[i] > pi) th1[i] -= *pi;
th2[i] = th - dth; if (th2[i] <= -pi) th2[i] += *pi;
if (th1[i] > th2[i]) std::swap(th1[i], th2[i]);
}
int ans = ;
ansv.push_back();
for (int i = ; i < n; i++) {
int l = , ans2 = -;
for (int j = ; j < n; j++)
if (i != j && (th1[j] < th1[i] || th1[j] > th2[i] || th2[j] < th1[i] || th2[j] > th2[i])
&& (th1[j] > th1[i] && th1[j] < th2[i] || th2[j] > th1[i] && th2[j] < th2[i])) {
if (th1[j] > th1[i] && th1[j] < th2[i]) {
a[l].first.first = th1[j] - th1[i];
a[l].first.second = th2[j] - th2[i];
} else {
a[l].first.first = th2[j] - th1[i];
a[l].first.second = th1[j] - th2[i];
}
if (a[l].first.second < ) a[l].first.second += *pi;
a[l].second = j;
l++;
}
std::sort(a, a + l);
for (int j = ; j < l; j++) b[j] = a[j].first.second;
std::sort(b, b + l);
for (int j = ; j <= l; j++) t[j] = ;
for (int j = ; j < l; j++) {
int p = std::lower_bound(b, b + l, a[j].first.second) - b + ;
int v = , v2 = -;
for (int k = p; k; k -= k&-k)
if (t[k] > v) v = t[k], v2 = t2[k];
v++;
f[a[j].second] = v2;
if (v+ > ans) ans = v+, ans2 = a[j].second;
for (int k = p; k <= l; k += k&-k)
if (t[k] < v) t[k] = v, t2[k] = a[j].second;
}
if (ans2 != -) {
ansv.clear();
while (ans2 != -)
ansv.push_back(ans2), ans2 = f[ans2];
ansv.push_back(i);
}
}
printf("%d\n", ans);
return ;
}