FJ省队集训DAY1 T1

题意:有一堆兔子，还有一个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 ;

 }