首页 > 代码库 > poj3819 Coverage （求直线与圆的交占直线的百分比 ）
poj3819 Coverage （求直线与圆的交占直线的百分比 ）
题意：给你一条直线和若干个圆，求圆与直线相交的长度占整条直线的比例
解题思路：通过定比分点的方法求出圆与直线的交占圆的比例。
第一步：(确定投影的方向是x轴还是y轴)
(1)当直线的line.s(x, y), line.e(x, y)的line.s.x与line.e.x不同时，这条直线可以等同于起点为line.s.x, line.e.x;
(2)不满足(1)时(即line.s.x==line.e.x时)，当直线的line.s(x, y), line.e(x, y)的line.s.y与line.e.y不同时，这条直线可以等同于起点为line.s.x, line.e.x;
(3)当不满足(1)以及(2)时(即line.s==line.e),这时候直线为一个点，任何的圆都与它没有交，圆占整条直线的比例为0；
第二步：(将圆投影到第一步得到的直线上)
求出圆在直线上的投影的范围；
第三步：
求出所有圆的并，将圆的并除以线段的长度，求圆与线段的交占线段的百分比；
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int MAX = 300;
struct Node
{
double x, y;
};
struct Line
{
Node s, e;
};
Line line;
Node p[MAX];
double A, B, C, delta;
double x, y, r;
double x11, y11, dx, dy;
Node tmp, cir;
double sqr(double x)
{
return x * x;
}
int circle_cross_line(Node s, Node e, Node O, double r)//判断圆与直线是否有交点
{
double x0 = O.x, y0=O.y;
x11 = s.x, y11 = s.y;
double x2 = e.x, y2 = e.y;
dx = x2 - x11, dy = y2 - y11;
A = dx * dx + dy*dy;
B = 2 * dx * (x11 - x0) + 2 * dy * (y11 - y0);
C = sqr(x11-x0) + sqr(y11-y0) - sqr(r);
delta = sqr(B) - 4 * A * C;
return delta > 0;
}
int cmp(Node a, Node b)
{
if (a.x < b.x)
return 1;
return 0;
}
int main()
{
int n, i, cnt;
int flag, flagnum;
double leng;
while (scanf("%d", &n) && n)
{
flagnum = 0;
scanf("%lf%lf%lf%lf", &line.s.x, &line.s.y, &line.e.x, &line.e.y);
if (line.s.x!=line.e.x)
{
if (line.s.x < line.e.x)
{
tmp.x = line.s.x;
tmp.y = line.e.x;
}
else
{
tmp.x = line.e.x;
tmp.y = line.s.x;
}
flag = 0;
leng = fabs(line.e.x - line.s.x);
}
else if (line.s.x==line.e.x && line.s.y!=line.e.y)
{
if (line.s.y < line.e.y)
{
tmp.x = line.s.y;
tmp.y = line.e.y;
}
else
{
tmp.x = line.e.y;
tmp.y = line.s.y;
}
flag = 1;
leng = fabs(line.e.y - line.s.y);
}
else
flagnum = 1;
cnt = 0;
for (i=0; i<n; i++)
{
scanf("%lf%lf%lf", &cir.x, &cir.y, &r);
if (flagnum)
continue;
if (circle_cross_line(line.s, line.e, cir, r))
{
p[cnt].x = (-B-sqrt(delta))/(2.0*A);
p[cnt].y = (-B+sqrt(delta))/(2.0*A);
if (flag==0)
{
p[cnt].x = p[cnt].x * dx + x11;
p[cnt].y = p[cnt].y * dx + x11;
}
else
{
p[cnt].x = p[cnt].x * dy + y11;
p[cnt].y = p[cnt].y * dy + y11;
}
if (p[cnt].x>p[cnt].y)
{
double t = p[cnt].x;
p[cnt].x = p[cnt].y;
p[cnt].y = t;
}
if (p[cnt].x>tmp.y || p[cnt].y<tmp.x)
continue;
if (p[cnt].x<tmp.x)
p[cnt].x = tmp.x;
if (p[cnt].y>tmp.y)
p[cnt].y = tmp.y;
cnt++;
}
}
if (flagnum || cnt==0)
printf("0.00\n");
else
{
sort(p, p+cnt, cmp);
double sum = 0;
tmp = p[0];
for (i=1; i<cnt; i++)
{
if (p[i].x < tmp.y)
{
if (p[i].y > tmp.y)
tmp.y = p[i].y;
}
else
{
sum += tmp.y - tmp.x;
tmp = p[i];
}
}
sum += tmp.y - tmp.x;
printf("%.2f\n", sum/leng*100.0);
}
}
return 0;
}
poj3819 Coverage （求直线与圆的交占直线的百分比 ）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。