POJ1673 ZOJ1776 三角形四心模板

POJ1673 题中所述点即为三角形的垂心，用向量法可以轻松证明。

垂心重心外心均位于三角形的欧拉线上，且三者有线性关系，于是，求出重心和外心即可求得垂心。

重心就是三点的平均值，外心可以通过解方程的方法简单求得。

给出代码

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

const double eps=1e-9;

int cmp(double x)

{

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

 if(x>0)return 1;

 	else return -1;

}

const double pi=acos(-1.0);

inline double sqr(double x)

{

 return x*x;

}

struct point

{

 double x,y;

 point (){}

 point (double a,double b):x(a),y(b){}

 void input()

 	{

 	 scanf("%lf%lf",&x,&y);

	}

 friend point operator +(const point &a,const point &b)

 	{

 	 return point(a.x+b.x,a.y+b.y);

	}

 friend point operator -(const point &a,const point &b)

 	{

 	 return point(a.x-b.x,a.y-b.y);

	}

 friend bool operator ==(const point &a,const point &b)

 	{

 	 return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0;

	}

 friend point operator *(const point &a,const double &b)

 	{

 	 return point(a.x*b,a.y*b);

	}

 friend point operator*(const double &a,const point &b)

 	{

 	 return point(a*b.x,a*b.y);

	}

 friend point operator /(const point &a,const double &b)

 	{

 	 return point(a.x/b,a.y/b);

	}

 double norm()

 	{

 	 return sqrt(sqr(x)+sqr(y));

	}

};

point Triangle_Mass_Center(point a,point b,point c)

{

 return(a+b+c)/3.;

}

point CircumCenter(point p0,point p1,point p2)

{

 point cp;

 double a1=p1.x-p0.x,b1=p1.y-p0.y,c1=(a1*a1+b1*b1)/2.;

 double a2=p2.x-p0.x,b2=p2.y-p0.y,c2=(a2*a2+b2*b2)/2.;

 double d=a1*b2-a2*b1;

 cp.x=p0.x+(c1*b2-c2*b1)/d;

 cp.y=p0.y+(a1*c2-a2*c1)/d;

 return cp;

}

point Orthocenter(point a,point b,point c)

{

 return Triangle_Mass_Center(a,b,c)*3.0-CircumCenter(a,b,c)*2.0;

}

point Innercenter(point a,point b,point c)

{

 point cp;

 double la,lb,lc;

 la=(b-c).norm();

 lb=(c-a).norm();

 lc=(a-b).norm();

 cp.x=(la*a.x+lb*b.x+lc*c.x)/(la+lb+lc);

 cp.y=(la*a.y+lb*b.y+lc*c.y)/(la+lb+lc);

 return cp;

}

int main()

{freopen("t.txt","r",stdin);

 int T;

 scanf("%d",&T);

 while(T--)

 	{

 	 point a,b,c;

 	 a.input();b.input();c.input();

 	 point ans=Orthocenter(a,b,c);

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

	}

 return 0;

}

　ZOJ1776 给定三角形求角平分线的交点（即内心）

内心坐标的公式如下。

首先证明这个结论：O是ABC内心的充要条件是：aOA+bOB+cOC=0 （均表示向量）
证明:OB=OA+AB,OC=OA+AC,代入aOA+bOB+cOC=0中得到：
AO=(bAB+cAC)/(a+b+c)
而|AC|=b,|AB|=c
所以AO=bc/(a+b+c) * (AB/|AB|+AC/|AC|)
而由平行四边形法则值(AB/|AB|+AC/|AC|)与BAC交角平分线共线
所以AO经过内心
同理BO,CO也经过内心,所以O为内心
反之亦然,就不证了
知道这个结论后
设ABC的坐标为：A(x1,y1),B(x2,y2),C(x3,y3) BC=a,CA=b,AB=c
内心为O(x,y)则有aOA+bOB+cOC=0（三个向量）
MA=(x1-x,y1-y)
MB=(x2-x,y2-y)
MC=(x3-x,y3-y)
则：a(x1-x)+b(x2-x)+c(x3-x)=0,a(y1-y)+b(y2-y)+c(y3-y)=0
∴x=(ax1+bx2+cx3)/(a+b+c),Y=(ay1+by2+cy3)/(a+b+c)
∴O((ax1+bx2+cx3)/(a+b+c),(ay1+by2+cy3)/(a+b+c))

代码如下

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<vector>

#include<iomanip>

using namespace std;

const double eps=1e-9;

int cmp(double x)

{

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

 if(x>0)return 1;

 	else return -1;

}

const double pi=acos(-1.0);

inline double sqr(double x)

{

 return x*x;

}

struct point

{

 long double x,y;

 point (){}

 point (long double a,long double b):x(a),y(b){}

 void input()

 	{

 	 char c;

 	 x=y=0.0;

 	 cin>>x>>c>>y;

	}

 friend point operator +(const point &a,const point &b)

 	{

 	 return point(a.x+b.x,a.y+b.y);

	}

 friend point operator -(const point &a,const point &b)

 	{

 	 return point(a.x-b.x,a.y-b.y);

	}

 friend bool operator ==(const point &a,const point &b)

 	{

 	 return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0;

	}

 friend point operator *(const point &a,const double &b)

 	{

 	 return point(a.x*b,a.y*b);

	}

 friend point operator*(const double &a,const point &b)

 	{

 	 return point(a*b.x,a*b.y);

	}

 friend point operator /(const point &a,const double &b)

 	{

 	 return point(a.x/b,a.y/b);

	}

 long double norm()

 	{

 	 return sqrt(sqr(x)+sqr(y));

	}

};

point Triangle_Mass_Center(point a,point b,point c)

{

 return(a+b+c)/3.;

}

point CircumCenter(point p0,point p1,point p2)

{

 point cp;

 double a1=p1.x-p0.x,b1=p1.y-p0.y,c1=(a1*a1+b1*b1)/2.;

 double a2=p2.x-p0.x,b2=p2.y-p0.y,c2=(a2*a2+b2*b2)/2.;

 double d=a1*b2-a2*b1;

 cp.x=p0.x+(c1*b2-c2*b1)/d;

 cp.y=p0.y+(a1*c2-a2*c1)/d;

 return cp;

}

point Orthocenter(point a,point b,point c)

{

 return Triangle_Mass_Center(a,b,c)*3.0-CircumCenter(a,b,c)*2.0;

}

point Innercenter(point a,point b,point c)

{

 point cp;

 long double la,lb,lc;

 la=(b-c).norm();

 lb=(c-a).norm();

 lc=(a-b).norm();

 cp.x=(la*a.x+lb*b.x+lc*c.x)/(la+lb+lc);

 cp.y=(la*a.y+lb*b.y+lc*c.y)/(la+lb+lc);

 return cp;

}

int main()

{freopen("t.txt","r",stdin);

 //freopen("1.txt","w",stdout);

 int T;

 while(cin>>T)

 {

 while(T--)

 	{

 	 point a,b,c;

 	 a.input();b.input();c.input();

 	 point ans=Innercenter(a,b,c);

 	 cout<<"("<<int(a.x)<<","<<int(a.y)<<")";

 	 cout<<"("<<int(b.x)<<","<<int(b.y)<<")";

 	 cout<<"("<<int(c.x)<<","<<int(c.y)<<"):";

 	 if(ans.x>eps)ans.x=floor(ans.x*10000)/10000.;

 	 	else ans.x=ceil(ans.x*10000)/10000.;

 	 if(ans.y>eps)ans.y=floor(ans.y*10000)/10000.;

 	 	else ans.y=ceil(ans.y*10000)/10000.;

     cout<<fixed<<setprecision(4);

 	 cout<<"("<<ans.x<<","<<ans.y<<")"<<endl;

	}

}

 return 0;

}

巴特西

POJ1673 ZOJ1776 三角形四心模板

最新文章

热门文章