●POJ 1329 Circle Through Three Points

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题链：

http://poj.org/problem?id=1329

题解：

计算几何，求过不共线的三点的圆

就是用向量暴力算出来的东西。。。

（设出外心M的坐标，由于$|\vec{MA}|=|\vec{MB}|=|\vec{MC}|$，可以解出M点坐标。）

代码：

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

const double eps=1e-8;

int sign(double x){

	if(fabs(x)<=eps) return 0;

	return x<0?-1:1;

}

void Pout(double x){//Print_Out

	if(sign(x)<0) printf(" - ");

	else printf(" + ");

	printf("%.3lf",fabs(x));

}

struct Point{

	double x,y;

	Point(double _x=0,double _y=0):x(_x),y(_y){}

	int Read(){return scanf("%lf%lf",&x,&y);}

};

typedef Point Vector;

Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}

Vector operator - (Point A,Point B){return Vector(A.x-B.x,A.y-B.y);}

double operator ^ (Vector A,Vector B){return A.x*B.y-A.y*B.x;}

double operator * (Vector A,Vector B){return A.x*B.x+A.y*B.y;}

struct Circle{

	Point o; double r;

	Circle(Point _o=Point(),double _r=0):o(_o),r(_r){}

	void PrintSE(){//Print_Standard_Equation

		printf("(x");Pout(-o.x);printf(")^2"); printf(" + ");

		printf("(y");Pout(-o.y);printf(")^2"); printf(" = ");

		printf("%.3lf^2\n",r);

	}

	void PrintNE(){//Print_Normal_Equation

		printf("x^2 + y^2");

		Pout(-2*o.x);printf("x");

		Pout(-2*o.y);printf("y");

		Pout(o.x*o.x+o.y*o.y-r*r);

		printf(" = 0\n\n");

	}

};

double GL(Vector A){//Get_Length

	return sqrt(A*A);

}

Circle GC(Point P1,Point P2,Point P3){//Get_Circle

	Vector B=P2-P1,C=P3-P1; Point P0;

	P0.x=((B*B)*C.y-(C*C)*B.y)/(2*(B^C))+P1.x;

	P0.y=((B*B)*C.x-(C*C)*B.x)/(2*(C^B))+P1.y;

	return Circle(P0,GL(P0-P1));

}

int main(){

	Point A,B,C;

	while(~A.Read()&&~B.Read()&&~C.Read()){

		GC(A,B,C).PrintSE();

		GC(A,B,C).PrintNE();

	}

	return 0;

}