[ZOJ3340 The Stars My Destination]海伦公式和勾股定理的妙用

【题目大意】
空间坐标系中(x,y,z)中:
给出一个射线和N个点。
求出和这个射线最远的点和射线的距离是多少。
【算法分析】
首先围观一下点到直线的距离怎么搞?
+_+。。。直接弄垂线不好搞啊。
于是弄一个三角形面积。再除以底边的长度,就可以得到高了。
面积可以用海伦公式。这样就什么都不需要了,只需要点与点之间的长度计算。

然后再YY一下射线,如果是高飘出射线,那个特定的角就会变钝角。(划一下就可以知道哪个角)
然后利用勾股定理a^2+b^2#include #include #include #include const int N=100005;
struct Point{int x,y,z;}pl[N],p1,p2;
int n;
double ans;

void input(){
scanf("%d%d%d",&p1.x,&p1.y,&p1.z);
scanf("%d%d%d",&p2.x,&p2.y,&p2.z);
for (int i=1;i<=n;i++)
scanf("%d%d%d",&pl[i].x,&pl[i].y,&pl[i].z);
}

inline double Sqr(double x){return x*x;}
inline double max(double x,double y){
if (x>y) return x;
else return y;
}
inline double min(double x,double y){
if (x else return y;
}

inline double dis(Point A,Point B){
return sqrt(Sqr(A.x-B.x)+Sqr(A.y-B.y)+Sqr(A.z-B.z));
}

inline void swap(double &x,double &y){
double tmp=x; x=y; y=tmp;
}

inline bool DunJiao(double a,double b,double c){
if (Sqr(a)+Sqr(b) return false;
}

void solve(){
int i,j,k;
double p,S,a,b,c,now;
ans=0;
for (i=1;i<=n;i++){
a=dis(p1,pl[i]); b=dis(p1,p2); c=dis(p2,pl[i]);
p=0.5*(a+b+c);
S=sqrt(p*(p-a)*(p-b)*(p-c));
now=min(a,c);
if (!DunJiao(a,b,c))
now=min(now,S*2/b);
ans=max(ans,now);
}
printf("%.2lfn",ans);
}

int main(){
while (scanf("%d",&n)!=EOF){
input();
solve();
}
}

加入对话

3条评论

留下评论

回复 gamegame151 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注