给你一些圆饼和木棍的位置和大小信息，让你按一定的顺序放置木棍：木棍只能放在圆饼上，或者放在之前已经放好的木棍上，要求放的时候需要此木棍保持平衡。平衡过的木棍就固定好了，不会动了。

   问你能不能找到一个顺序放置完所有的木棍。

解题报告：

摘自：http://blog.sina.com.cn/s/blog_5123df350100rff6.html

关键看对于稳定的理解……把线段从中间截断成两段。那么看每条小线段是否稳定。

小线段稳定如果：（1） 它和一条已经稳定的线段有公共点。 或者（2） 它和某一个圆盘有公共点。

（圆盘的意思是圆形的区域而不仅仅是边界）。 如果两条小线段都满足稳定条件，整条线段是稳定的。

就这么不断地扩散，稳定线段不断增多，如果能否使得所有线段都稳定。复杂度O(n2)。

代码如下：

 

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int t, n, m;

#define eps 1e-9

#define SIZE 102

struct pint

{

    pint(double x, double y):x(x), y(y){}

    pint(){}

    double x,y;

};

struct Cir{pint c; double r;} cir[SIZE];

struct Line{pint a, b;} line[SIZE];

double xmult(pint p1,pint p2,pint p0){

return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);

}

double direction(pint p1, pint p2, pint p3)

{

    return (p3.x - p1.x) * (p2.y - p1.y) - (p2.x - p1.x) * (p3.y - p1.y);

}

double dist(pint p1,pint p2){

return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));

}

double disptoline(pint p,pint l1,pint l2){

return fabs(xmult(p,l1,l2))/dist(l1,l2);

}

int intersect_seg_circle(pint c,double r,pint l1,pint l2){

double t1=dist(c,l1)-r,t2=dist(c,l2)-r;

pint t=c;

if (t1<eps||t2<eps)

return true;

t.x+=l1.y-l2.y;

t.y+=l2.x-l1.x;

return xmult(l1,c,t)*xmult(l2,c,t)<eps&&disptoline(c,l1,l2)-r<eps;

}

int myeps(double xx)

{

    if (fabs(xx) <= eps) return 0;

    else if (xx > 0) return 1;

    else return -1;

}

bool online(pint p1, pint p2, pint p3)

{

    return (p3.x >= min(p1.x, p2.x) && p3.x <= max(p1.x, p2.x) && p3.y >= min(p1.y, p2.y) && p3.y <= max(p1.y, p2.y));

}

bool insect(pint p1, pint p2, pint p3, pint p4)

{

    double d1 = xmult(p1, p4, p3);

    double d2 = xmult(p2, p4, p3);

    double d3 = xmult(p3, p2, p1);

    double d4 = xmult(p4, p2, p1);

    if (myeps (d1) * myeps (d2) < 0 && myeps (d3) * myeps (d4) < 0) return true;

    else if (myeps (d1) == 0 && online(p3, p4, p1)) return true;

    else if (myeps (d2) == 0 && online(p3, p4, p2)) return true;

    else if (myeps (d3) == 0 && online(p1, p2, p3)) return true;

    else if (myeps (d4) == 0 && online(p1, p2, p4)) return true;

    return false;

}

int que[SIZE], vst[SIZE];

int main()

{

    scanf("%d", &t);

    while(t--)

    {

        scanf("%d%d", &n, &m);

        for(int i = 0; i < n; i++)

        {

            int a, b, c;scanf("%d%d%d", &a, &b, &c);

            cir[i].c = pint(a, b); cir[i].r = c;

        }

        for(int i = 0; i < m; i++)

            scanf("%lf%lf%lf%lf", &line[i].a.x, &line[i].a.y, &line[i].b.x, &line[i].b.y);

        int head = 0, tail = 0;

        memset(vst, 0, sizeof(vst));

        bool flag = true;

        while(flag)

        {

            flag = false;

            for(int i = 0; i < m; i++)

                if (!vst[i])

                {

                    bool l = false, r = false;

                    pint mid = pint((line[i].a.x + line[i].b.x) * 0.5, (line[i].a.y + line[i].b.y) * 0.5);

                    for(int j = 0; j < n; j++)

                    {

                        if (intersect_seg_circle(cir[j].c, cir[j].r, line[i].a, mid))l = true;

                        if (intersect_seg_circle(cir[j].c, cir[j].r, line[i].b, mid))r = true;

                    }

                    for(int j = 0; j < tail; j++)

                    {

                        if (insect(line[i].a, mid, line[que[j]].a, line[que[j]].b)) l = true;

                        if (insect(line[i].b, mid, line[que[j]].a, line[que[j]].b)) r = true;

                    }

                    if (l && r)

                        que[tail++] = i,vst[i] = true,flag = true;

                }

        }

        if (tail == m) printf("YES\n");

        else printf("NO\n");

    }

    return 0;

}