HDU - 4720 -- Naive and Silly Muggles: 三角形的外心

题意

有三个巫师和麻瓜，三个巫师的三个坐标形成一个圆，如果麻瓜在这个圆中（包含边界），那么将是危险的，否则是安全的。

思路

直接求三角形外心，然后判断外心与麻瓜的距离与半径的大小即可。

AC代码

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false)
const double eps = 1e-8;
struct Point{
    double x, y;
    Point(double x=0, double y=0):x(x), y(y) {}
};
double sqr(double x){
	return x*x;
}
double dis(Point a,Point b){ //求ab的长度 
	return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
Point operator+(Point a,Point b){  //向量加 
	return Point(a.x+b.x,a.y+b.y);  
} 
Point operator-(Point a,Point b){ //向量减
	return Point(a.x-b.x,a.y-b.y);
} 
void Swap(Point *a, Point *b) {
	Point temp = *a;
	*a = *b;
	*b = temp;
}
Point Circum(Point a,Point b,Point c){ //三角形外心 
	double x1=a.x,y1=a.y;
	double x2=b.x,y2=b.y;
	double x3=c.x,y3=c.y;
	
	double a1=2*(x2-x1);
	double b1=2*(y2-y1);
	double c1=x2*x2+y2*y2-x1*x1-y1*y1;
	
	double a2=2*(x3-x2);
	double b2=2*(y3-y2);
	double c2=x3*x3+y3*y3-x2*x2-y2*y2;
	
	double x=(c1*b2-c2*b1)/(a1*b2-a2*b1);
	double y=(a1*c2-a2*c1)/(a1*b2-a2*b1);
	
	return Point(x,y);
} 
void solve() {
	double x1, y1, x2, y2, x3, y3, x, y;
	scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3, &x, &y);
	Point p1 = Point(x1, y1), p2 = Point(x2, y2), p3 = Point(x3, y3);
	double len12 = dis(p1, p2);
	double len13 = dis(p1, p3);
	double len23 = dis(p2, p3);
	if (len12 < len13) swap(len12, len13), Swap(&p2, &p3);
	if (len12 < len23) swap(len12, len23), Swap(&p1, &p3);
	if (len13 < len23) swap(len13, len23), Swap(&p1, &p2);
	//len12 >= len13 >= len23
	Point p;
	if (sqr(len12) > sqr(len13) + sqr(len23)) {
		p = (Point((x1 + x2) / 2, (y1 + y2) / 2));
	} else {
		p = Circum(Point(x1, y1), Point(x2, y2), Point(x3, y3));
	}
	double px1 = dis(p, Point(x1, y1));
	double px2 = dis(p, Point(x, y));
	if (px2 > px1) {
		puts("Safe");
	} else {
		puts("Danger");
	}
}
int main() {
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; ++i) {
		printf("Case #%d: ", i);
		solve();
	}
	return 0;
}