POJ 3808 Malfatti Circles(计算几何)

Malfatti Circles
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 250   Accepted: 125   Special Judge

Description

The con?guration of three circles packed inside a triangle such that each circle is tangent to the other two circles and to two of the edges of the triangle has been studied by many mathematicians for more than two centuries. Existence and uniqueness of such
circles for an arbitrary triangle are easy to prove. Many methods of numerical calculation or geometric construction of such circles from an arbitrarily given triangle have been discovered. Today, such circles are called the Malfatti circles. 

Figure 7 illustrates an example. The Malfatti circles of the triangle with the vertices (20, 80), (⑷0, ⑵0) and (120, ⑵0) are approximately 
the circle with the center (24.281677, 45.219486) and the radius 21.565935, 
the circle with the center (3.110950, 4.409005) and the radius 24.409005, and 
the circle with the center (54.556724, 7.107493) and the radius 27.107493. 

Figure 8 illustrates another example. The Malfatti circles of the triangle with the vertices (20, ⑵0), (120, ⑵0) and (⑷0, 80) are approximately 
the circle with the center (25.629089, ⑴0.057956) and the radius 9.942044, 
the circle with the center (53.225883, -0.849435) and the radius 19.150565, and 
the circle with the center (19.701191, 19.203466) and the radius 19.913790. 

Your mission is to write a program to calculate the radii of the Malfatti circles of the given triangles. 

Input

The input is a sequence of datasets. A dataset is a line containing six integers x1, y1, x2, y2, x3 and y3 in this order, separated by a space. The coordinates of the vertices of the given triangle are (x1, y1), (x2, y2) and (x3, y3), respectively. You can
assume that the vertices form a triangle counterclockwise. You can also assume that the following two conditions hold. 

All of the coordinate values are greater than ⑴000 and less than 1000. 
None of the Malfatti circles of the triangle has a radius less than 0.1. 

The end of the input is indicated by a line containing six zeros separated by a space.

Output

For each input dataset, three decimal fractions r1, r2 and r3 should be printed in a line in this order separated by a space. The radii of the Malfatti circles nearest to the vertices with the coordinates (x1, y1), (x2, y2) and (x3, y3) should be r1, r2 and
r3, respectively. 

None of the output values may have an error greater than 0.0001. No extra character should appear in the output.

Sample Input

20 80 ⑷0 ⑵0 120 ⑵0
20 ⑵0 120 ⑵0 ⑷0 80
0 0 1 0 0 1
0 0 999 1 ⑼99 1
897 ⑼16 847 ⑼72 890 ⑼25
999 999 ⑼99 ⑼98 ⑼98 ⑼99
⑼99 ⑼99 999 ⑼99 0 731
⑼99 ⑼99 999 ⑷64 ⑷64 999
979 ⑷36 ⑼55 ⑶37 157 ⑷39
0 0 0 0 0 0

Sample Output

21.565935 24.409005 27.107493
9.942044 19.150565 19.913790
0.148847 0.207107 0.207107
0.125125 0.499750 0.499750
0.373458 0.383897 0.100456
0.706768 0.353509 0.353509
365.638023 365.638023 365.601038
378.524085 378.605339 378.605339
21.895803 22.052921 5.895714

题意:给出1个3角形的3个顶点的坐标,求3角形的3个内切圆,它们两两相切,并且每一个顶点附近的圆和连接这个顶点的两条边也相切。求着3个内切圆的半径。

分析:套公式。

其中r为3角形内切圆的半径,s为半周长。

#include <cstdio>
#include <cmath>
using namespace std;

struct Point {
double x, y;
} A, B, C, I;

double get_dis(Point p1, Point p2) {
return sqrt((p1.x – p2.x) * (p1.x – p2.x) + (p1.y – p2.y) * (p1.y – p2.y));
}

int main() {
while(~scanf("%lf%lf%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y, &C.x, &C.y)) {
if(A.x == 0 && A.y == 0 && B.x == 0 && B.y == 0 && C.x == 0 && C.y == 0) break;
double a = get_dis(B, C);
double b = get_dis(A, C);
double c = get_dis(A, B);
double s = (a + b + c) / 2; // 半周长
I.x = (a * A.x + b * B.x + c * C.x) / (a + b + c);
I.y = (a * A.y + b * B.y + c * C.y) / (a + b + c); // 内切圆圆心坐标
double r = sqrt((s – a) * (s – b) * (s – c) / s); // 内切圆半径
double IA = get_dis(A, I);
double IB = get_dis(B, I);
double IC = get_dis(C, I);
double r1 = r / (2 * (s – a)) * (s – r + IA – IB – IC);
double r2 = r / (2 * (s – b)) * (s – r + IB – IA – IC);
double r3 = r / (2 * (s – c)) * (s – r + IC – IA – IB);
printf("%.6lf %.6lf %.6lf
", r1, r2, r3);
}
return 0;
}

更多解释请见http://en.wikipedia.org/wiki/Malfatti_circles

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » POJ 3808 Malfatti Circles(计算几何)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡