计算几何，暴力。
题目中有一句话：$The$ $mass$ $of$ $each$ $brick$ $is$ $equally$ $distributed$ $and$ $it$ $will$ $be$ $stable$ $if$ $it$ $is$ $placed$ $on$ $bases$ $or$ $stable$ $bricks$ $and$ $the$ $moment$ $of$ $it$ $can$ $be$ $zero$ $when$ $it$ $is$ $placed$.
核心原则：左右半段均有稳定的东西支撑，这条才算是稳定的。暴力扩展就可以了。需要用到判断线段不严格相交以及点到线段的最小距离。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<ctime> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0); void File() { freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout); } template <class T> inline void read(T &x) { char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); } } const double eps=1e-10; #define zero(x)(((x)>0?(x):(-x))<eps) struct point { double x,y; point(double X,double Y) { x=X; y=Y; } }; double xmult(point p1,point p2,point p0) { return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); } int dots_inline(point p1,point p2,point p3) { return zero(xmult(p1,p2,p3)); } int same_side(point p1,point p2,point l1,point l2) { return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps; } int dot_online_in(point p,point l1,point l2) { return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps; } int intersect_in(point u1,point u2,point v1,point v2) { if(!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2)) return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2); return dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2); } int T; struct YUAN { double x,y,r; } yuan[200]; struct XIAN { double p1x,p1y,p2x,p2y; } xian[200]; int n,m; int f[200]; double DIS(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } point intersection(point u1,point u2,point v1,point v2) { point ret=u1; double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x)) /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x)); ret.x+=(u2.x-u1.x)*t; ret.y+=(u2.y-u1.y)*t; return ret; } point ptoseg(point p,point l1,point l2) { point t=p; t.x+=l1.y-l2.y,t.y+=l2.x-l1.x; if(xmult(l1,t,p)*xmult(l2,t,p)>eps) return DIS(p,l1)<DIS(p,l2)?l1:l2; return intersection(p,t,l1,l2); } int check(point A,point B,int b) { point F=ptoseg(point(yuan[b].x,yuan[b].y),A,B); double dis=DIS(F,point(yuan[b].x,yuan[b].y)); if(dis<=yuan[b].r) return 1; return 0; } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) scanf("%lf%lf%lf",&yuan[i].x,&yuan[i].y,&yuan[i].r); for(int i=1; i<=m; i++) scanf("%lf%lf%lf%lf",&xian[i].p1x,&xian[i].p1y,&xian[i].p2x,&xian[i].p2y); memset(f,0,sizeof f); int sum=0; while(1) { int Z=0; for(int i=1; i<=m; i++) { if(f[i]==1) continue; point p1= point(xian[i].p1x,xian[i].p1y); point p2= point(xian[i].p2x,xian[i].p2y); point p3= point((p1.x+p2.x)/2,(p1.y+p2.y)/2); int f1=0,f2=0; for(int j=1; j<=n; j++) { if(check(p1,p3,j)) f1=1; if(check(p2,p3,j)) f2=1; } for(int j=1; j<=m; j++) { if(f[j]==0) continue; if(intersect_in(p1,p3,point(xian[j].p1x,xian[j].p1y),point(xian[j].p2x,xian[j].p2y))) f1=1; if(intersect_in(p2,p3,point(xian[j].p1x,xian[j].p1y),point(xian[j].p2x,xian[j].p2y))) f2=1; } if(f1==1&&f2==1) f[i]=1,Z++; } if(Z==0) break; sum=sum+Z; } if(sum!=m) printf("NO\n"); else printf("YES\n"); } return 0; }
原文：http://www.cnblogs.com/zufezzt/p/6384482.html