這個算法真心玄學(xué)匈挖，網(wǎng)上還一堆假代碼碾牌，假博客QAQ，還有并軟用的樣例儡循。舶吗。。
還是總結(jié)總結(jié)吧
這次有四道題用了模擬退火Ellipsoid（也可以三分套三分）择膝、Run Away誓琼、Groundhog Build Home、A Chocolate Manufacturer's Problem
常用
計算單個點到已知所有點的最值等問題
注意點
1肴捉、所有類型用double !!!!!腹侣。。齿穗。有三題分別WA在函數(shù)形參用int傲隶，中途變量用int，定義數(shù)組用int缤灵。伦籍。這種錯誤蓝晒，在自己編譯的時候編譯器幫你強制轉(zhuǎn)化了，放到OJ上就GG
2帖鸦、根據(jù)題目要求的精度芝薇，設(shè)計T，delta和隨機次數(shù)作儿，太小了容易精度不夠洛二，太大了就容易TLE
3、GetVal的計算一定要仔細攻锰，筆者基本都是這里出錯
4晾嘶、HDU的。娶吞。垒迂。注意是多case！多case妒蛇！多case机断！
5、不要漏要求輸出的任何字符Ｐ宥帷吏奸！
接下來就發(fā)發(fā)題解
HDU 5017Ellipsoid
題意大致是求從原點到橢圓面的最短距離
解法大概有三分套三分，模擬退火陶耍。奋蔚。。正所謂學(xué)了假高數(shù)烈钞，不會拉格朗日定理的我只能退火了
/*坑點大概就是一開始看了一份假題解
后來WA就是沒考慮方程的負解
還有就是參數(shù)類型錯誤泊碑，一定要用double
*/
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL long long
#define CLR(x) memset(x, 0, sizeof(x))
const double INF = 1e10;
const double eps = 1e-9;
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; //因為是三維坐標所有有八個方向走
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
double a, b, c, d, e, f;
double dist(double x, double y, double z)
{
return sqrt(x*x + y*y + z*z);
}
double GetVal(double x, double y)
{ //啦啦解方程
double A = c;
double B = e*x + d*y;
double C = a*x*x + b*y*y + f*x*y-1;
double D = B*B - 4*A*C;
if (D < 0) return INF;
double det = sqrt(D);
double res1 = (-B + det) / (2*A);
double res2 = (-B - det) / (2*A);
return dist(x,y,res1) < dist(x,y,res2) ? res1 : res2;
}
double Search()
{
double T = 1; //初始溫度
double delta = 0.99;
double x = 0, y = 0, z = sqrt(1/c);
while (T > eps)
{
for (int i = 0; i < 8; i++)
{
double r = x + dx[i]*T;
double c = y + dy[i]*T;
double k = GetVal(r, c);
if (k > INF) continue;
if (dist(r,c,k) < dist(x,y,z))
{
x = r;
y = c;
z = k;
}
}
T *= delta;
}
return dist(x, y, z);
}
int main()
{
while(scanf("%lf%lf%lf%lf%lf%lf", &a, &b, &c, &d, &e, &f) != EOF)
{
printf("%.7lf\n", Search());
}
}
HDU 1109Run Away
大致題意，給n個點棵磷，在平面內(nèi)選一個點A蛾狗，使A到所有點的距離和最小，并求最小距離仪媒。
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <time.h>
#include <iostream>
using namespace std;
#define LL long long
#define CLR(x) memset(x, 0, sizeof(x))
const double INF = 1e8;
const double eps = 1e-3;
int dx[5] = {-1, 0, 1, 0}; //平面內(nèi)
int dy[5] = {0, 1, 0, -1};
double X, Y;
int M;
double U[1005], V[1005];
struct node //數(shù)組和結(jié)構(gòu)體都可用
{
double x, y;
double val;
} p[55];
double dist(double x, double y, double a, double b)
{
return (x-a)*(x-a) + (y-b)*(y-b);
}
double GetSum(node h)
{
double d = INF;
for (int i = 0; i < M; i++)
d = min(d, dist(h.x, h.y, U[i], V[i]));
return d;
}
double Search()
{
double T = X+Y;
double delta = 0.9;
for (int i = 0; i <= 50; i++)
{
p[i].x = (rand()%1000+1) * 1.0/1000.00 * X; //隊內(nèi)dalao說可以暴力，不用隨機
p[i].y = (rand()%1000+1) * 1.0/1000.00 * Y;
p[i].val = GetSum(p[i]);
}
node tmp;
while (T > eps)
{
for (int i = 0; i <= 50; i++)
{
for (int j = 0; j <= 50; j++)
{
double r = (double)(rand()%1000+1)*1.0/1000.00*T;
double c = sqrt(T*T - r*r);
if (rand()&1) r *= -1;
if (rand()&1) c *= -1;
tmp.x = p[i].x + r;
tmp.y = p[i].y + c;
if (tmp.x<0 || tmp.x>X || tmp.y<0 || tmp.y>Y) continue;
if (GetSum(tmp) > p[i].val)
{
p[i] = tmp;
p[i].val = GetSum(tmp);
}
}
}
T *= delta;
}
int cur = 1;
for (int i = 0; i <= 50; i++)
if (p[i].val > p[cur].val)
cur = i;
printf("The safest point is (%.1lf, %.1lf).\n", p[cur].x, p[cur].y);
//不要漏了句號Ｐ蝗怠Ｋ惴浴！佃扼！血一般的教訓(xùn)
}
int main()
{
srand(unsigned(time(0)));
int t;
scanf("%d", &t);
while(t--)
{
CLR(U);
CLR(V);
scanf("%lf%lf%d", &X, &Y, &M);
for (int i = 0; i < M; i++)
scanf("%lf%lf", &U[i], &V[i]);
Search();
}
}
HDU 3932Groundhog Build Home
大致題意是一直土撥鼠要找一個離他所有朋友家都最近的點偎巢，并輸出到最近朋友家的最大距離。
其實就是平面上的最小圓覆蓋問題兼耀，這種單點到多點的用退火很很合適压昼，然后就是求冷，為了避免局域最大值印象答案，在這題和下一題窍霞，筆者都用分塊隨機數(shù)
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL long long
#define CLR(x) memset(x, 0, sizeof(x))
#define MAX 100000000*1LL
#define PI acos(-1)
const double eps = 1e-2;
const double INF = 1e8;
double X, Y;
int N;
double px[1005], py[1005];
struct node
{
double x, y, val;
} p[1005];
double dist(double x, double y, double a, double b)
{
return sqrt((x-a)*(x-a) + (y-b)*(y-b));
}
double GetMax(node t)
{
double d = 0;
for (int i = 0; i < N; i++)
d = max(d, dist(t.x, t.y, px[i], py[i])); //注意匠题，這里是最大值
return d;
}
void Search()
{
double delta = 0.6; //！５稹韭山！太接近1會TLE
double T = max(X, Y);
node tmp;
while(T > eps)
{
for(int i = 0; i < N; i++)
{
for(int j = 0; j < 20; j++) //這里也是，過大會TLE
{
double d = (rand()%1000+1)/1000.0*2*PI;
tmp.x = p[i].x + cos(d)*T;
tmp.y = p[i].y + sin(d)*T;
if (tmp.x<=0 || tmp.x>=X || tmp.y<=0 || tmp.y>=Y) continue;
if (GetMax(tmp) < p[i].val)
{
p[i] = tmp;
p[i].val = GetMax(tmp);
}
}
}
T *= delta;
}
node res;
res.val = INF;;
for (int i = 0; i < N; i++) // 求出全局最優(yōu)解
if (p[i].val < res.val) res = p[i];
printf("(%.1lf,%.1lf).\n", res.x, res.y);
printf("%.1lf\n", res.val);
}
int main()
{
srand(unsigned(time(0)));
while(scanf("%lf%lf%d", &X, &Y, &N) != EOF)
{
CLR(px);
CLR(py);
for (int i = 0; i < N; i++)
scanf("%lf%lf", &px[i], &py[i]);
for (int i = 0; i < N; i++) /*隨機取N個點冷溃。钱磅。。筆者原本是最直接改上一題的代碼似枕。盖淡。。
結(jié)果出事情了凿歼。禁舷。。事實告訴我們隨機數(shù)要謹慎*/
{
p[i].x = (rand()%1000+1)/1000.0*X;
p[i].y = (rand()%1000+1)/1000.0*Y;
p[i].val = GetMax(p[i]);
}
Search();
}
}
HDU 3644A Chocolate Manufacturer's Problem
大致題意求一個多邊形內(nèi)最大的內(nèi)接圓
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL long long
#define CLR(x) memset(x, 0, sizeof(x))
#define MAX 100000000*1LL
#define PI 3.14159265358
//#define zero(x) (((x)>0?(x):(-x))<eps)
const double eps = 1e-3;
const double INF = 1e8;
int n;
double R;
double MidX, MidY;
struct node
{
double x, y;
double R;
} p[105];
int zero(double x)
{ //不知道什么緣故毅往，宏定義出事故了牵咙。
if (fabs(x) < eps) return 0;
else return x > 0 ? 1 : -1;
}
double dist(node a, node b)
{
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
double cross(node k1, node k2, node k0)
{
return (k1.x-k0.x)*(k2.y-k0.y) - (k2.x-k0.x)*(k1.y-k0.y);
}
double Disptosege(node& l1, node& l2, node& k ) //求解點到線段的距離！攀唯！
{
double a, b, c;
a = dist(l1, k);
b = dist(l2, k);
c = dist(l1, l2);
if(zero(a*a+c*c-b*b) < 0) return a;
else if(zero(b*b+c*c-a*a) < 0) return b;
else return fabs(cross(k, l1, l2)/c);
}
bool inside_convex(node a) //判斷點是不是在多邊形內(nèi)
{
int cnt = 0;
double tmp;
for(int i = 0; i < n; i++)
{
if( (p[i].y<=a.y && p[i+1].y>a.y) || (p[i+1].y<=a.y && p[i].y>a.y))
{
if (zero(p[i].y-p[i+1].y))
tmp = p[i+1].x - (p[i+1].x-p[i].x)*(p[i+1].y-a.y)/(p[i+1].y-p[i].y);
else
{
if(!zero(p[i].y-a.y)) cnt++;
tmp = -INF;
}
if(zero(tmp - a.x) >= 0) cnt++;
}
}
return cnt&1;
}
void cal(node& a)
{
double t;
a.R = INF;
for( int i = 0; i < n; ++i )
{
t = Disptosege(p[i], p[i+1], a);
a.R = min(a.R, t);
}
}
node mid[105];
void Search()
{
bool flag = false;
double delta = 0.90;
double T = sqrt(MidX*MidX + MidY*MidY)/2.0;
int k = 0;
while(!flag && T > eps)
{
for (int i = 0; i < n; i++)
{
k++;
if (flag) break;
for (int j = 0; j < 5; j++)
{
if (flag) break;
node tmp;
double angle = rand();
tmp.x = mid[i].x + cos(angle)*T;
tmp.y = mid[i].y + sin(angle)*T;
if (inside_convex(tmp))
{
cal(tmp);
if (tmp.R > mid[i].R)
{
mid[i] = tmp;
//mid[i].R = GetVal(tmp);
if (zero(tmp.R - R) >= 0) flag = true;
}
}
}
}
T *= delta;
}
//printf("%d\n", k);
if (flag) printf("Yes\n");
else printf("No\n");
}
int main()
{
//srand(unsigned(time(0)));
while(scanf("%d", &n)==1 && n)
{
double MaxX=0, MaxY = 0;
double MinX=INF, MinY=INF;
for (int i = 0; i < n; i++)
{
scanf("%lf%lf", &p[i].x, &p[i].y);
MaxX = max(MaxX, p[i].x);
MaxY = max(MaxY, p[i].y);
MinX = min(MinX, p[i].x);
MinY = min(MinY, p[i].y);
}
MidX = MaxX - MinX;
MidY = MaxY - MinY;
scanf("%lf", &R);
p[n] = p[0];
for (int i = 0; i < n; i++)
{
mid[i].x = (p[i].x + p[i+1].x) / 2; //取中點
//隊內(nèi)一位dalao取右上點也過了洁桌，但是左下點一定WA
mid[i].y = (p[i].y + p[i+1].y) / 2;
mid[i].R = 0;
}
Search();
}
}
總結(jié)
數(shù)據(jù)只能判斷大體沒問題，概率侯嘀，溫度另凌，如何隨機去點還是要根據(jù)情況定，如何逼近最優(yōu)解
