poj1673——求三角形的垂心

题目链接：http://poj.org/problem?id=1673

Given a triangle ABC, the Extriangles of ABC are constructed as follows:
On each side of ABC, construct a square (ABDE, BCHJ and ACFG in the figure below).
Connect adjacent square corners to form the three Extriangles (AGD, BEJ and CFH in the figure).
The Exomedians of ABC are the medians of the Extriangles, which pass through vertices of the original triangle,extended into the original triangle (LAO, MBO and NCO in the figure. As the figure indicates, the three Exomedians intersect at a common point called the Exocenter (point O in the figure).
This problem is to write a program to compute the Exocenters of triangles.

Input

The first line of the input consists of a positive integer n, which is the number of datasets that follow. Each dataset consists of 3 lines; each line contains two floating point values which represent the (two -dimensional) coordinate of one vertex of a triangle. So, there are total of (n*3) + 1 lines of input. Note: All input triangles wi ll be strongly non-degenerate in that no vertex will be within one unit of the line through the other two vertices.

Output

For each dataset you must print out the coordinates of the Exocenter of the input triangle correct to four decimal places.

Sample Input

2
0.0 0.0
9.0 12.0
14.0 0.0
3.0 4.0
13.0 19.0
2.0 -10.0

Sample Output

9.0000 3.7500
-48.0400 23.3600

题意理解：

给你n个三角形每个点的坐标，求出这个三角形的垂心，直接套公式就行了。（自己可以证明一下）

下面给出求常见三角形的各种点的代码：

//外心
point circumcenter(point a, point b, point c){
	line u, v;
	u.a.x = (a.x + b.x) / 2;
	u.a.y = (a.y + b.y) / 2;
	u.b.x = u.a.x - a.y + b.y;
	u.b.y = u.a.y + a.x - b.x;
	v.a.x = (a.x + c.x) / 2;
	v.a.y = (a.y + c.y) / 2;
	v.b.x = v.a.x - a.y + c.y;
	v.b.y = v.a.y + a.x - c.x;
	return intersection(u, v);
}

//内心
point incenter(point a, point b, point c){
	line u, v;
	double m, n;
	u.a = a;
	m = atan2(b.y - a.y, b.x - a.x);
	n = atan2(c.y - a.y, c.x - a.x);
	u.b.x = u.a.x + cos((m + n) / 2);
	u.b.y = u.a.y + sin((m + n) / 2);
	v.a = b;
	m = atan2(a.y - b.y, a.x - b.x);
	n = atan2(c.y - b.y, c.x - b.x);
	v.b.x = v.a.x + cos((m + n) / 2);
	v.b.y = v.a.y + sin((m + n) / 2);
	return intersection(u, v);
}

//垂心
point perpencenter(point a, point b, point c){
	line u, v;
	u.a = c;
	u.b.x = u.a.x - a.y + b.y;
	u.b.y = u.a.y + a.x - b.x;
	v.a = b;
	v.b.x = v.a.x - a.y + c.y;
	v.b.y = v.a.y + a.x - c.x;
	return intersection(u, v);
}

//重心
//到三角形三顶点距离的平方和最小的点
//三角形内到三边距离之积最大的点
point barycenter(point a, point b, point c){
	line u, v;
	u.a.x = (a.x + b.x) / 2;
	u.a.y = (a.y + b.y) / 2;
	u.b = c;
	v.a.x = (a.x + c.x) / 2;
	v.a.y = (a.y + c.y) / 2;
	v.b = b;
	return intersection(u, v);
}

//费马点
//到三角形三顶点距离之和最小的点
point fermentpoint(point a, point b, point c){
	point u, v;
	double step = fabs(a.x) + fabs(a.y) + fabs(b.x) + fabs(b.y) + fabs(c.x) + fabs(c.y);
	int i, j, k;
	u.x = (a.x + b.x + c.x) / 3;
	u.y = (a.y + b.y + c.y) / 3;
	while (step > 1e-10)
		for (k = 0; k < 10; step /= 2, k++)
			for (i = -1; i <= 1; i++)
				for (j = -1; j <= 1; j++){
					v.x = u.x + step*i;
					v.y = u.y + step*j;
					if (distance(u, a) + distance(u, b) + distance(u, c) > distance(v, a) + distance(v, b) + distance(v, c))
						u = v;
				}
				return u;
}

下面是这个题的代码。 

#include<iostream>
using namespace std;
struct point{
	double x,y;
	point(double x=0,double y=0):x(x),y(y){}
};
struct line{ point a, b; };

point intersection(line u, line v){
	point ret = u.a;
	double t = ((u.a.x - v.a.x)*(v.a.y - v.b.y) - (u.a.y - v.a.y)*(v.a.x - v.b.x))
		/ ((u.a.x - u.b.x)*(v.a.y - v.b.y) - (u.a.y - u.b.y)*(v.a.x - v.b.x));
	ret.x += (u.b.x - u.a.x)*t;
	ret.y += (u.b.y - u.a.y)*t;
	return ret;
}
point perpencenter(point a, point b, point c){
	line u, v;
	u.a = c;
	u.b.x = u.a.x - a.y + b.y;
	u.b.y = u.a.y + a.x - b.x;
	v.a = b;
	v.b.x = v.a.x - a.y + c.y;
	v.b.y = v.a.y + a.x - c.x;
	return intersection(u, v);
}
int main(){
	int n;
	scanf("%d",&n);
	while(n--){
		point p1,p2,p3;
		scanf("%lf%lf",&p1.x,&p1.y);
		scanf("%lf%lf",&p2.x,&p2.y);
		scanf("%lf%lf",&p3.x,&p3.y);
		
		point p=perpencenter(p1,p2,p3);
		printf("%.4f %.4f\n",p.x,p.y);
	}
	return 0;
}