学步园

在平面给出许多半径不一的圆，求一条直线最多能穿过多少个圆。

求出每两个圆间的四条公切线，并保存角度值，并用1和-1标记这四条直线何时是进两圆范围，何时是出两圆范围。然后按斜率排序切线，扫一遍，通过标记计算什么时候通过的圆最多。

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>

using namespace std;

const double eps = 1e-8;
const int N = 2010;
const double pi = acos(-1.0);

inline int sig(double x)
{
    return (x > eps) - (x < -eps);
}

typedef struct Point
{
    double x, y;
    Point () {}
    Point (double _x, double _y):
        x(_x), y(_y) {}
    void in()
    {
        scanf("%lf%lf", &x, &y);
    }
    double dis()
    {
        return sqrt(x * x + y * y);
    }
}Vector;

Vector operator -(const Vector &a, const Vector &b)
{
    return Vector(a.x - b.x, a.y - b.y);
}

Vector operator +(const Vector &a, const Vector &b)
{
    return Vector(a.x + b.x, a.y + b.y);
}

struct Circle
{
    Point o;
    double r;
    Circle () {}
    Circle (Point _o, double _r):
        o(_o), r(_r) {}
    void in()
    {
        o.in();
        scanf("%lf", &r);
    }
};

Circle cc[N];

struct Line
{
    double ang;
    int t;
    Line () {}
    Line (double _ang, int _t):
        ang(_ang), t(_t) {}
    void out()
    {
        printf("%.2lf %d\n", ang, t);
    }
    bool operator <(const Line &a) const
    {
        return (sig(ang - a.ang) == 0 ? t > a.t : sig(ang - a.ang) < 0);
    }
};

Line ss[N<<2];

int cnt, n;

void tan(Circle a, Circle b)
{
    double d = (a.o - b.o).dis();
    double rdif = a.r - b.r;
    double rsum = a.r + b.r;
    
    double base = atan2((b.o).y - (a.o).y, (b.o).x - (a.o).x);
    double ang = acos(rdif / d);
    ss[cnt++] = Line(base + ang, -1);
    ss[cnt++] = Line(base - ang, 1);
    
    if(sig(d - rsum) > 0)
    {
        ang = acos(rsum / d);
        ss[cnt++] = Line(base + ang, 1);
        ss[cnt++] = Line(base - ang, -1);
    }
    return ;
}

void solve()
{
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        cnt = 0;
        for(int j = 0; j < n; j++)
        {
            if(i == j)
                continue;
            tan(cc[i], cc[j]);
        }
        sort(ss, ss + cnt);
        //printf("cnt == %d  i == %d\n", cnt, i);
        //for(int j = 0; j < cnt; ++j) ss[j].out();
        int ma = 0;
        for(int j = 0; j < cnt; j++)
        {
            if(ss[j].t == 1)
                ma++;
            else
                ma--;
            ans = max(ma, ans);            
        }
    }
    printf("%d\n", ans + 1);
    return ;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--) 
    {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) 
            cc[i].in();
        solve();
    }
    return 0;
}