1673.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"math.h"

const double pi = acos(-1);

//点的定义
struct point
{
	Type x,y;
	point(){x=y=0;}
	point(Type x,Type y):x(x),y(y){;}
	bool operator==(point &a){return x==a.x&&y==a.y;}
};
//叉乘
inline Type cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
inline Type cheng(point b,point c)
{return b.x*c.y-c.x*b.y;}

//直线定义
struct line
{
	point a,b;
	line(){;}
	line(point &x,point &y):a(x),b(y){;}
};
point rotate(double alpha,point z,point o )
{
	point c;
	double cosa=cos(alpha),sina=sin(alpha);
	z.x -= o.x;
	z.y -= o.y;
	c.x=z.x*cosa-z.y*sina +o.x;
	c.y=z.x*sina+z.y*cosa +o.y;
	return c;
}

point crosspoint(line l1,line l2)
{
	Type p1=cheng(l2.a,l1.a,l2.b),
		 p2=cheng(l2.a,l2.b,l1.b);
	if(p1+p2==0)return l1.a;
	point c;
	c.x=(p1*l1.b.x+p2*l1.a.x)/(p1+p2);
	c.y=(p1*l1.b.y+p2*l1.a.y)/(p1+p2);
	return c;
}
int main( )
{
	int n;
	point a, b, c, d, e, j, g, o;
	scanf( "%d", &n );	
	while( n-- )
	{
		scanf( "%lf %lf", &a.x, &a.y );
		scanf( "%lf %lf", &b.x, &b.y );
		scanf( "%lf %lf", &c.x, &c.y );

		g = rotate( 3*pi/2, c, a );
		d = rotate( pi/2, b, a );

		e = rotate( 3*pi/2, a, b );
		j = rotate( pi/2, c, b );

		o = crosspoint( line( a, point( (g.x+d.x)/2, (g.y+d.y)/2 ) ), 
			line( b, point( (e.x+j.x)/2, (e.y+j.y)/2 ) ) );

		printf( "%.4lf %.4lf\n", o.x, o.y );
	}

	return 0;
}