題意:
求一個四邊形的費馬點。
分析:
模擬退火要麼超時要麼wa,這題的數據就是不想讓隨機算法過的。。其實四邊形的費馬點很簡單,如果是凸四邊形的話費馬點是對角線交點,如果是凹四邊形費馬點是凹點。但題目給的四個點順序是不確定的,所以要先求下凸包。
代碼:
//poj 3990 //sep9 #include#include #include using namespace std; struct Point { double x,y,v; Point(){} Point(double x,double y):x(x),y(y){} }pnt[8],rec[8]; double getSum(Point p) { double sum=0; for(int i=0;i<4;++i) sum+=sqrt((p.x-pnt[i].x)*(p.x-pnt[i].x)+(p.y-pnt[i].y)*(p.y-pnt[i].y)); return sum; } int cmp(Point a,Point b) { if(a.y!=b.y) return a.y 0?1:-1; } double dis(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int cross(Point a,Point b,Point c) { double x1=b.x-a.x; double y1=b.y-a.y; double x2=c.x-a.x; double y2=c.y-a.y; return dbl(x1*y2-x2*y1); } int graham() { int n=4; sort(pnt,pnt+n,cmp); rec[0]=pnt[0]; rec[1]=pnt[1]; int i,pos=1; for(i=2;i 0&&cross(rec[pos-1],rec[pos],pnt[i])<=0) --pos; rec[++pos]=pnt[i]; } int bak=pos; for(i=n-1;i>=0;--i){ while(pos>bak&&cross(rec[pos-1],rec[pos],pnt[i])<=0) --pos; rec[++pos]=pnt[i]; } return pos; } int main() { int i; while(1){ for(i=0;i<4;++i) scanf("%lf%lf",&pnt[i].x,&pnt[i].y); double ans=0; if(pnt[0].x<-0.5) break; if(graham()==4){ ans+=dis(rec[0],rec[2]); ans+=dis(rec[1],rec[3]); } else{ ans=1e10; for(int i=0;i<4;++i) ans=min(ans,getSum(pnt[i])); } printf("%.4lf\n",ans+1e-8); } return 0; }