本文主要是介绍BNU 7536 HDU 3425 Coverage (圆与直线相交 )TeamContest - 4—B【解题报告】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目链接】click here~~
【题目大意】求多个圆与线段相交的部分占整个线段的百分比。
【解题思路】
此题首先要判断圆心不一定全在给定的线段上，可以在任意的位置，(理解错了题，原先以为圆心在线段上，读题要仔细！)
因此我们可以联立圆的方程和线段的方程首先判断线段与圆有没有交点
求出方程组解得：
二次项系数为 a = cos(cx1,cx0) +cos(cy1,cy0);//二次项的系数
一次项系数为 b = 2*((cx0-x)*(cx1-cx0) + (cy0-y)*(cy1-cy0));
以及常数项为 c = cos(cx0,x)+cos(cy0,y)-r*r;
(cos(a,b)=(a-b)*(a-b)),不是余弦函数
最后用求根方式判断有无交点
解出两个解为 bi1，bi2为在线段上的比例点。
第二步：
求出比例点之后，我们就可以用贪心的区间覆盖问题筛选出所有符合条件的区间，最后累加即可
代码：
#include <bits/stdc++.h>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
struct node
{double x,y,left,right;
} Map[105];
bool cmp(node a, node b)
{if(a.left==b.left) return a.right<b.right; //定义与线段的左交点和右交点。并从左往右排序return a.left < b.left;
}
double solve(double a) //方程根的判断
{if(a<0) return 0;if(a>1) return 1;return a;
}
double cos(double a,double b)
{return (a-b)*(a-b);
}
int main()
{int n,m,i,j;double cx0, cy0, cx1, cy1;double x, y, r;double a, b, c, d, bi1, bi2;while(cin>>n&&n){cin>>cx0>>cy0>>cx1>>cy1;int res= 0;for(i = 0; i < n; i ++){cin >> x >> y >> r;a = cos(cx1,cx0) +cos(cy1,cy0); //二次项的系数b = 2*((cx0-x)*(cx1-cx0) + (cy0-y)*(cy1-cy0));//一次项的系数c = cos(cx0,x)+cos(cy0,y)-r*r; //常数项的系数d = b*b-4*a*c; //求解直线与圆相交方程if (d<= 0) continue;bi1=solve((-b+sqrt(d))/(2*a)); //根的判定bi2=solve((-b-sqrt(d))/(2*a));if(bi2 < bi1) swap(bi1, bi2);Map[res].left=bi1; // bi1，bi2为在线段上的比例点。Map[res ++].right=bi2;}if(res==0){ //如果所有圆不与线段相交{cout<<"0.00"<<endl;continue;}sort(Map,Map+res,cmp); //将圆半径从小到大排序double ans= 0, bi1= Map[0].left, bi2=Map[0].right;//初始化赋值for(i=1;i<res;i++) { // 区间覆盖{if(Map[i].left>bi2){ //如果之后的圆的左交点大于右交点，更新右交点，同时累加区间和ans+=bi2-bi1;bi1=Map[i].left;bi2=Map[i].right;}else{bi2=max(bi2,Map[i].right); //否则，取最大的右交点，更新右交点}}ans+=bi2-bi1;printf("%.2f\n", ans*100);}return 0;
}
这篇关于BNU 7536 HDU 3425 Coverage (圆与直线相交 )TeamContest - 4—B【解题报告】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
