本文主要是介绍POJ 1329 Circle Through Three Points,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
链接:http://poj.org/problem?id=1329
题目:
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 3176 | Accepted: 1347 |
Description
The solution is to be printed as an equation of the form
(x - h)^2 + (y - k)^2 = r^2 (1)
and an equation of the form
x^2 + y^2 + cx + dy - e = 0 (2)
Input
Output
Sample Input
7.0 -5.0 -1.0 1.0 0.0 -6.0 1.0 7.0 8.0 6.0 7.0 -2.0
Sample Output
(x - 3.000)^2 + (y + 2.000)^2 = 5.000^2 x^2 + y^2 - 6.000x + 4.000y - 12.000 = 0(x - 3.921)^2 + (y - 2.447)^2 = 5.409^2 x^2 + y^2 - 7.842x - 4.895y - 7.895 = 0
解题思路:
计算几何,模板题,关键就是求三角形的外心,
(x,y)为圆心坐标:
已知三个点的坐标是:(x1,y1),(x2,y2), (x3,y3);
A2 = x2 - x1, B2 = y2 - y1, A3 = x3 - x1, B3 = y3 - y1,C2 = (x2 * x2 - x1*x1 + y2 * y2 - y1 * y1), C3 = (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1);
x = (C2 * B3 - C3 * B2) / (B3 * A2 - A3 * B2) / 2;
y = (C2 * A3 - C3 * A2) / (B2 * A3 - B3 * A2) / 2;
r = sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
代码:
#include <cstdio>
#include <cmath>
using namespace std;struct Point
{double x, y;
};Point a, b, c;
double x, y, r;void fun()
{double A2 = b.x - a.x, B2 = b.y - a.y;double C2 = b.y * b.y - a.y * a.y + b.x * b.x - a.x * a.x;double A3 = c.x - a.x, B3 = c.y - a.y;double C3 = c.y * c.y - a.y * a.y + c.x * c.x - a.x * a.x;x = (C2 * B3 - C3 * B2) / (B3 * A2 - A3 * B2) / 2;y = (C2 * A3 - C3 * A2) / (B2 * A3 - B3 * A2) / 2;r = sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y));
}int main()
{while(~scanf("%lf%lf%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y, &c.x, &c.y)){fun();printf("(x ");printf("%c", x > 0 ? '-' : '+');printf(" %.3f)^2 + (y ", fabs(x));printf("%c", y > 0 ? '-' : '+');printf(" %.3f)^2 = %.3f^2\n", fabs(y), r);printf("x^2 + y^2 ");printf("%c", -2 * x > 0 ? '+' : '-');printf(" %.3fx ", fabs(-2 * x));printf("%c", -2 * y > 0 ? '+' : '-');printf(" %.3fy ", fabs(-2 * y));printf("%c", x * x + y * y - r *r > 0 ? '+' : '-');printf(" %.3f = 0\n\n", fabs(x * x + y * y - r * r));}return 0;
}
这篇关于POJ 1329 Circle Through Three Points的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!