題目地址 ：http://acm.hdu.edu.cn/showproblem.php?pid=4720

題目是給三個點 ，要求求出最小的能覆蓋這三個點的圓，然后判斷第四個點在不在這個圓內(nèi)。

如果這個是一個鈍角三角形，那么圓心就是最長邊的中點，如果是銳角三角形，圓心就是外接圓圓心。 然后用點到圓心的距離和半徑的關(guān)系判斷是不是在圓內(nèi)。

求外接圓時 用到向量點積為0，還有Crammer法則解方程

代碼：

#include<iostream> #include<cstdio> using namespace std;double calcdet(double p[2][2] ) //計算行列式的值 {double ans=p[0][0]*p[1][1]-p[1][0]*p[0][1];return ans; } int main() {double xa,ya,xb,yb,xc,yc,xm,ym,xd,yd,xe,ye,b1,b2; //d是ab中點 e是ac中點int T;cin>>T;int index=0;while(T--){scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&xa,&ya,&xb,&yb,&xc,&yc,&xm,&ym);double ac=(xa-xc)*(xa-xc)+(ya-yc)*(ya-yc);double ab=(xa-xb)*(xa-xb)+(ya-yb)*(ya-yb);double bc=(xb-xc)*(xb-xc)+(yb-yc)*(yb-yc);double x,y;int tag=0;if(ac+ab<=bc){x=(xb+xc)/2;y=(yb+yc)/2;tag++;}else if(ac+bc<=ab){x=(xa+xb)/2;y=(ya+yb)/2;tag++;}else if(bc+ab<=ac){x=(xa+xc)/2;y=(ya+yc)/2;tag++;}if(tag==0){double p[2][2];p[0][0]=xb-xa;p[0][1]=yb-ya;p[1][0]=xc-xa;p[1][1]=yc-ya;xd=(xa+xb)/2;yd=(ya+yb)/2;xe=(xa+xc)/2;ye=(ya+yc)/2;b1=xd*(xb-xa)+yd*(yb-ya);b2=xe*(xc-xa)+ye*(yc-ya);double D=calcdet(p);p[0][0]=b1;p[1][0]=b2;double Dx=calcdet(p);p[0][0]=xb-xa;p[0][1]=b1;p[1][0]=xc-xa;p[1][1]=b2;double Dy=calcdet(p);x=Dx/D;y=Dy/D;}double R=(xa-x)*(xa-x)+(ya-y)*(ya-y);double dis=(xm-x)*(xm-x)+(ym-y)*(ym-y);index++;cout<<"Case #"<<index<<": ";if(dis>R) cout<<"Safe"<<endl;else cout<<"Danger"<<endl;} }

轉(zhuǎn)載于:https://www.cnblogs.com/jingqi814/p/3581600.html

總結(jié)

以上是生活随笔為你收集整理的13成都邀请赛 1005 Naive and Silly Muggles的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。