被这道题玩死了要。。。
对每个圆枚举得到和其他圆切线斜率，两个切线之间的斜率范围是可以经过的。得到的许多斜率范围可以转化为区间覆盖，nlogn排序得解，总复杂度O(n^2logn)。
要特别处理圆相交、包含的情况。
切线的斜率范围，是按 -pi~pi 算的，算晕了很久。。
然后就是恐怖的TLE，最后发现交C++TLE，交G++就过了，额滴个神，累死了，调一晚上。。
还有，这题用sort比用qsort快了5s。。。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 const int maxn = 1 << 10 | 1; 9 const double pi = acos(-1.0); 10 const double eps = 1e-6; 11 typedef struct 12 { 13 double x, y, r; 14 } Cir; 15 typedef struct 16 { 17 double site; 18 bool se; 19 } Seg; 20 Cir ra[maxn]; 21 Seg s[maxn << 3]; 22 int n, stp, ans; 23 inline double max(double a, double b) 24 { 25 return a > b ? a : b; 26 } 27 inline double min(double a, double b) 28 { 29 return a < b ? a : b; 30 } 31 inline double CalDis(double a, double b) 32 { 33 return sqrt(a * a + b * b); 34 } 35 inline bool IinJ(int i, int j, double ijdis) 36 { 37 return ra[i].r + ijdis <= ra[j].r; 38 } 39 inline bool IcutJ(int i, int j, double ijdis) 40 { 41 return ijdis <= ra[i].r + ra[j].r; 42 } 43 void AddSeg(double start, double end) 44 { 45 if(start + pi < -eps) start += 2 * pi; 46 if(start - pi > -eps) start -= 2 * pi; 47 if(end + pi < -eps) end += 2 * pi; 48 if(end - pi > -eps) end -= 2 * pi; 49 if(start - end > eps) AddSeg(start, pi - eps * 2), AddSeg(-pi, end); 50 else 51 { 52 s[stp].site = start, s[stp].se = 1; 53 ++ stp; 54 s[stp].site = end, s[stp].se = 0; 55 ++ stp; 56 } 57 } 58 int comp(const void *a, const void *b) 59 { 60 if(fabs((*(Seg *)a).site - (*(Seg *)b).site) < eps) 61 return -((*(Seg *)a).se && !(*(Seg *)b).se); 62 return (*(Seg *)a).site > (*(Seg *)b).site ? 1 : -1; 63 } 64 /* 65 //sort 66 bool comp(const Seg &a, const Seg &b) 67 { 68 if(fabs(a.site - b.site) < eps) 69 return a.se && !b.se; 70 return a.site < b.site; 71 } 72 */ 73 void Cal(int i) 74 { 75 int sum, j; 76 for(j = sum = stp = 0; j < n; ++ j) 77 { 78 if(i != j) 79 { 80 double ijdis = CalDis(ra[i].x - ra[j].x, ra[i].y - ra[j].y); 81 double xlij = atan2(ra[i].y - ra[j].y, ra[i].x - ra[j].x); 82 double xlji = atan2(ra[j].y - ra[i].y, ra[j].x - ra[i].x); 83 double asipj = asin((ra[i].r + ra[j].r) / ijdis); 84 double asimj = asin((ra[i].r - ra[j].r) / ijdis); 85 if(IinJ(i, j, ijdis)) ++ sum; 86 else if(IinJ(j, i, ijdis)); 87 else if(IcutJ(i, j, ijdis)) AddSeg(xlij + asimj, xlji - asimj); 88 else 89 { 90 AddSeg(xlji - asipj, xlji - asimj); 91 AddSeg(xlij + asimj, xlij + asipj); 92 } 93 } 94 } 95 qsort(s, stp, sizeof(Seg), comp); 96 // sort(s, s + stp, comp); 97 for(i = 0; i < stp; ++ i) 98 { 99 if(s[i].se) ++ sum;100 else -- sum;101 if(sum > ans) ans = sum;102 }103 if(sum > ans) ans = sum;104 }105 int main()106 {107 int t, ca, i;108 for(scanf("%d", &t), ca = 1; ca <= t; ++ ca)109 {110 scanf("%d", &n);111 for(i = 0; i < n; ++ i)112 scanf("%lf%lf%lf", &ra[i].x, &ra[i].y, &ra[i].r);113 for(i = ans = 0; i < n; ++ i) Cal(i);114 printf("Case #%d: %d\n", ca, ans + 1);115 }116 return 0;117 }