POJ 2420 模拟退火法

Description

Input

Output

Sample Input

4
0 0
0 10000
10000 10000
10000 0

Sample Output

28284

在多边形内找一个点，使得到多边形各个点的距离和最小，显然是费马点，模拟退火法

代码：

/* ***********************************************
Author :_rabbit
Created Time :2014/5/3 16:37:48
File Name :8.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
struct Point{
	double x,y;
	Point(double _x=0,double _y=0){
		x=_x;y=_y;
	}
};
int dcmp(double x){
	if(fabs(x)<eps)return 0;
	return x<0?-1:1;
}
Point operator + (Point a,Point b){
	return Point(a.x+b.x,a.y+b.y);
}
Point operator - (Point a,Point b){
	return Point(a.x-b.x,a.y-b.y);
}
Point operator * (Point a,double p){
	return Point(a.x*p,a.y*p);
}
Point operator / (Point a,double p){
	return Point(a.x/p,a.y/p);
}
bool operator <(const Point &a,const Point &b){
	return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
bool operator == (const Point &a,const Point  &b){
	return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double Dot(Point a,Point b){
	return a.x*b.x+a.y*b.y;
}
double Length(Point a){
	return sqrt(Dot(a,a));
}
double Angle(Point a,Point b){
	return acos(Dot(a,b)/Length(a)/Length(b));
}
double angle(Point a){
	return atan2(a.y,a.x);
}
double Cross(Point a,Point b){
	return a.x*b.y-a.y*b.x;
}
Point Rotate(Point a,double rad){
	return Point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
Point GetLineIntersection(Point p,Point v,Point q,Point w){
	Point u=p-q;
	double t=Cross(w,u)/Cross(v,w);
	return p+v*t;
}
Point perpencenter(Point a,Point b,Point c){
	Point A,B,C,D;
	A=c;
	B.x=c.x-a.y+b.y;
	B.y=c.y+a.x-b.x;
	C=b;
	D.x=b.x-a.y+c.y;
	D.y=b.y+a.x-c.x;
	return GetLineIntersection(A,B-A,C,D-C);
}
Point pp[110];
int main(){
	int n;
	while(cin>>n){
		for(int i=1;i<=n;i++)scanf("%lf%lf",&pp[i].x,&pp[i].y);
		double ans=INF,step=0;
		Point u,v;
		u.x=u.y=v.x=v.y=0;
		for(int i=1;i<=n;i++){
			step+=fabs(pp[i].x)+fabs(pp[i].y);
			u.x+=pp[i].x;
			u.y+=pp[i].y;
		}
		u=u/n;
		for(;step>eps;step/=2){
			for(int i=-4;i<=4;i++)
				for(int j=-4;j<=4;j++){
					v.x=u.x+step*i;
					v.y=u.y+step*j;
					double cnt=0;
					for(int p=1;p<=n;p++)cnt+=Length(v-pp[p]);
					if(cnt<ans){
						ans=cnt;
						u=v;
					}
				}
		}
		int hh;
		double ss=ans-(int)ans;
		if(ss<0.5)hh=(int)ans;else hh=(int)ans+1;
		printf("%d\n",hh);
	}
}

POJ 2420 模拟退火法,布布扣,bubuko.com

POJ 2420 模拟退火法

原文：http://blog.csdn.net/xianxingwuguan1/article/details/24931295