程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3990 Fermat Point in Quadrangle 凸包和費馬點

poj 3990 Fermat Point in Quadrangle 凸包和費馬點

編輯:C++入門知識

poj 3990 Fermat Point in Quadrangle 凸包和費馬點


題意:

求一個四邊形的費馬點。

分析:

模擬退火要麼超時要麼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.y0?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;i0&&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;	
} 


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved