首页 > POJ解题报告 > POJ 2420 A Star not a Tree? 多边形费马点

POJ 2420 A Star not a Tree? 多边形费马点

POJ 2420 A Star not a Tree?实际上就是求平面内多边形的费马点问题,只不过这里要的不是点,而是最短距离。这里使用模拟退火的方法来逼近费马点。所谓费马点就是指满足这样条件的一个点:这个点到多边形所有定点的距离和最短。

平面上三角形的费马点有如下性质:

  1. 若三角形ABC的3个内角均小于120°,那么3条距离连线正好平分费马点所在的周角。
  2. 若三角形有一内角不小于120度,则此钝角的顶点就是距离和最小的点。

这次福州赛区考了个四边形的费马点,但是我们悲剧的卡在了Wrong Answer,使得我们打铁而归,郁闷的要死,至今都不明白是哪里出了问题。看来RP不是一般的差。

/*
	Author:  代码疯子
	Blog:    http://www.programlife.net/
	Problem: POJ2420
	Keyword: 费马点,模拟退火
*/
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

#define MAX_NUM 128

typedef struct TagPoint
{
	double x;
	double y;
}Point;

inline double pt_distance(Point a, Point b)
{
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

double fermat_point(Point pt[], int n, Point& ptres)
{
	Point u, v;
	double step = 0.0, curlen, explen, minlen;
	int i, j, k, idx;
	bool flag;
	u.x = u.y = v.x = v.y = 0.0;
	for(i = 0; i < n; ++i)
	{
		step += fabs(pt[i].x) + fabs(pt[i].y);
		u.x += pt[i].x;
		u.y += pt[i].y;
	}
	u.x /= n;
	u.y /= n;
	flag = 0;
	while(step > 1e-10)
	{
		for(k = 0; k < 10; step /= 2, ++k)
			for(i = -1; i <= 1; ++i)
				for(j = -1; j <= 1; ++j)
				{
					v.x = u.x + step*i;
					v.y = u.y + step*j;
					curlen = explen = 0.0;
					for(idx = 0; idx < n; ++idx)
					{
						curlen += pt_distance(u, pt[idx]);
						explen += pt_distance(v, pt[idx]);
					}
					if(curlen > explen)
					{
						u = v;
						minlen = explen;
						flag = 1;
					}
				}
	}
	ptres = u;
	return flag ? minlen : curlen;
}

int main(int argc, char **argv)
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	
	int n, i;
	double res;
	Point pt[MAX_NUM], ptres;
	while(EOF != scanf("%d", &n))
	{
		for(i = 0; i < n; ++i)
		{
			scanf("%lf %lf", &pt[i].x, &pt[i].y);
		}
		res = fermat_point(pt, n, ptres);
		if(res-(int)(res) > 0.5)
			printf("%d\n", (int)(res+1));
		else
			printf("%d\n", (int)(res));
	}
	
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> POJ 2420 A Star not a Tree? 多边形费马点
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 本文目前尚无任何评论.