圆形几何上的建模计算的问题,运用C语言的程序的设计的方式如何实现计算的?

Problem Description
We'll consider an interesting geometric problem here. Given a number of circles with varying radius on the plane, and define the P-value of a point (x, y) on the plane as the number of circles covering this point. Here, by "covering", we mean that the point is either strictly within the circle, or on the boundary of the circle.
Given the starting position (Sx, Sy), and the destination position (Tx, Ty), please find a path between the two points, such that every point of the path is on the boundary of one or more circles, and the absolute difference between the maximum P-value and the minimum P-value among all points on the path is minimized.
Can you find the minimum absolute value with the help of your computer?

Input
There are multiple test cases in the input file. Each test case starts with one integer N (1 <= N <= 150), the number of circles, followed by four real numbers, Sx, Sy, Tx, Ty, representing the x-coordinate and y-coordinate of the starting position and the destination. Each of the following N lines consists of three real numbers X, Y and R (R >= 1), indicating that there is a circle at position (X, Y) with radius R.
There is a blank line after each test case. Input ends with End-of-File.
Note: It is guaranteed that the input data is always legal, i.e. both the starting position and the destination are on the boundary of one or more circles, no two circles will be at the same position, every real number in the input file has at most three digits after the decimal point, and the absolute value of any real number does not exceed 10000.

Output
For each test case, output one integer on one separate line as requested. If there is no way to reach the destination, output -1 instead.

Sample Input
2
-1.000 0.000 1.000 0.000
0.000 0.000 1.000
1.000 0.000 1.000

2
-1.000 0.000 5.000 0.000
-1.000 -1.000 1.000
4.000 0.000 1.000

Sample Output
Case 1: 1
Case 2: -1

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!

相似问题

1
如何计算一条线过哪几个网格
2
如何计算一个多边形与哪些网格相交
1
最大三角形, 这个题目怎么做
0
基于FDTD模拟一维磁场 电场
1
一个几何上角度的计算问题,用了很多思路都不能解决,C语言
3
出构成的最大的三角形的面积,结果保留两位小数。C语言,谢谢
0
运用C语言技术,输出构成的最大的三角形的面积,结果保留两位小数
0
这个问题,用C语言输出构成的最大的三角形的面积,结果保留两位小数。
0
采用算法计算一个几何问题,计算围栏的长度怎么用C语言程序的实现的方式
0
几何平方距离的判断,输出的序列式怎么算,采用C程序的方式
0
几何对称和最小剪裁次数的算法问题,如何利用C语言计算的
0
几何图形的相交的判断的问题,要求求出相交图形的名字,用C语言进行
0
圆面上的扇形和环的切割几何问题的一个算法,采用C语言编程怎么才能比较好的实现
0
几何折叠坐标的90度旋转的算法问题,如何利用C语言的编程方法实现这个
1
要求在这些点里寻找三个点,使他们构成的三角形拥有的面积最大,如何运用C语言技术的编程手段
0
一个算法要求在这些点里寻找三个点,使他们构成的三角形拥有的面积最大,用C语言怎么实现
0
几何图形的重心的问题的寻找问题,利用C语言的办法怎么实现的呢
1
CATIA的CAA二次开发的相关问题
0
使用C语言编程工具,输出构成的最大的三角形的面积,结果保留两位小数
0
计算一个几何图形的重心的坐标位置,用C语言程序设计的过程怎么做?