【题目描述】 小雪和小可可被困在了一个无限大的迷宫中。 已经知道这个迷宫有 N 堵环状的墙，如果把整个迷宫看作是一个二维平面，那么每一堵墙都是平面上一个圆。任意两个圆不相交，不重合，也不会相切， 但有可能相互包含。小雪和小可可分别被困在了 2 个不同的位置，且保证他们的位置与这些圆不重合。 他们只有破坏墙面才能穿过去。 小雪希望知道，如果他们要相见，至少要破坏掉多少堵墙？他们可以在任何位置相见。 【输入格式】 第一行有一个整数 N，表示有多少堵墙，保证 0<=N<=8000。 之后 N 行，每一行有三个整数 x， y 和 r，表示有一堵环状的墙是以(x,y)为圆形， r为半径的。保证-100000000<=x,y,r<=100000000。 再下一行有一个整数 Q，表示有多少组询问，保证 1<=Q<=8000。 之后 Q 行，每一行有 4 个整数 a， b， c 和 d，给出了一组询问，表示小雪所在的位置为(a,b)，小可可所在的位置为(c,d)。保证-100000000<=a,b,c,d<=100000000。 【输出格式】 输出 Q 行，对应 Q 次询问，每一行输出一个整数，表示最小需要破坏掉多少堵墙才能相见。 【样例输入】 3 0 0 1 0 0 2 4 0 1 2 0 0 4 0 0 0 0 4 【样例输出】 3 2 【分析】 对于两个点和一个圆，只有4种情况： 1.A点在圆内，B点在圆外：必须穿过一个圆 2.A点在圆内，B点在圆内：不用穿过圆 3.A点在圆外，B点在圆外：不用穿过圆 4.A点在圆外，B点在圆内：必须穿过一个圆 如何判断一个点是否在圆内呢？求出点到圆心的距离d，判断d是否小于圆的半径即可。
#include<cstdio> typedef long long ll; ll x[8005],y[8005],r[8005]; int n,q,a,b,c,d; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld%lld%lld",x+i,y+i,r+i); scanf("%d",&q); while(q--) { scanf("%d%d%d%d",&a,&b,&c,&d); int ans=0; for(int i=1;i<=n;i++) ans+=((a-x[i])*(a-x[i])+(b-y[i])*(b-y[i])<=r[i]*r[i])+((c-x[i])*(c-x[i])+(d-y[i])*(d-y[i])<=r[i]*r[i])==1; printf("%d\n",ans); } return 0; }转载于:https://www.cnblogs.com/JRX2015U43/p/6533472.html
