UVA190 Circle Through Three Points（计算几何）

题目大意：

给你三个不共线的点，求过三点圆的方程。写出一般式和标准式。

思路：

这题要求我们求出过给定三个点的圆的两个方程，一个是标准式，一个是一般式。 标准式：(x-h)^2+(y-k)2=r^2 一般式：x^2+y2+cx+dy-e=0; 学过三角形的同学都能知道，三角形的外心过三角形三点，所以圆心就是三角形外心，然后半径为一个点到圆心的距离。这样标准式答案就出来了。(h,k)是圆心坐标，r是半径。

对于一般式，学过圆的同学应该也知道，没学过的同学吧标准式化简一下也可以得到一般式。

这题最难得地方在于如何求出三角形的外心。当然可以用斜率，求出三角形任意两条线段的中垂线交点，不过比较复杂，因为斜率可能不存在，还要求交点什么的。我们可以使用向量来运算。 我们设3个点位p1(x1,y1),p2(x2,y2),p3(x3,y3)该三角形的外接圆圆心为p(x,y)

对于边向量p1p2（箭头不会打…） Ap1p2=x2-x1 Bp1p2=y2-y1 Cp1p2=-|p1p2|/2; 对于边向量同理。 那么三角形边p1p2的中垂线与p1p3的中垂线交点p=(x1,y1*)，其中

x1=-(Cp1p3Bp1p2-Cp1p2Bp1p3)/(Ap1p3Bp1p2-Bp1p3*Ap1p2);

y1=-(Cp1p3Ap1p2-Cp1p2Ap1p3)/(Bp1p3Ap1p2-Ap1p3*Bp1p2);

显然圆心为p=p1+p*；

程序：

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;

struct Point{
	double x,y;
	
	Point(double _x=0,double _y=0):x(_x),y(_y) {}
	
	Point operator -(const Point &op2) const {
		return Point(x-op2.x,y-op2.y);
	}
	
	Point operator +(const Point &op2) const {
		return Point(x+op2.x,y+op2.y);
	}
	
	Point operator /(const double d) const {
		return Point(x/d,y/d);
	}
	
	Point operator *(const double d) const{
		return Point(x*d,y*d);
	}
	
	double operator ^(const Point &op2) const {
		return x*op2.y-y*op2.x;
	}	
};

struct StraightLine{
	double A,B,C;
	StraightLine(double _a=0,double _b=0,double _c=0):A(_a),B(_b),C(_c){}
	Point cross(const StraightLine &a) const {
		double xx=-(C*a.B-a.C*B)/(A*a.B-B*a.A);
		double yy=-(C*a.A-a.C*A)/(B*a.A-a.B*A);
		return Point(xx,yy);
	}
};

inline double sqr(double x){
	return x*x;
}

inline double dis2(const Point &p1,const Point &p2){
	return sqr(p1.x-p2.x)+sqr(p1.y-p2.y);
}

inline double dis(const Point &p1,const Point &p2){
	return sqrt(dis2(p1,p2));
}

inline double mul(const Point &p1,const Point &p2,const Point &p3){
	return (p2-p1)^(p3-p1);
}

inline double circumcenter(const Point &p1,const Point &p2,const Point &p3,Point &p){
	p=p1+StraightLine(p3.x-p1.x,p3.y-p1.y,-dis2(p3,p1)/2.0).cross(StraightLine(p2.x-p1.x,p2.y-p1.y,-dis2(p2,p1)/2.0));
	return dis(p,p1);
}

Point p1,p2,p3,p;

inline int print(double x){
	if (x>0) printf(" + %.3lf",x);
	else printf(" - %.3lf",-x);
	return 0;
}

int main(){
	freopen("a.in","r",stdin);
	while (cin>>p1.x>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y){
		double r=circumcenter(p1,p2,p3,p);
		printf("(x");
		print(-p.x);
		printf(")^2 + (y");
		print(-p.y);
		printf(")^2 =");
		printf(" %.3lf",r);
		printf("^2\n");
		printf("x^2 + y^2");
		print(-2*p.x);
		printf("x");
		print(-2*p.y);
		printf("y");
		print(sqr(p.x)+sqr(p.y)-sqr(r));
		printf(" = 0\n\n");
	}
}