传送门 --Vjudge https://vjudge.net/problem/POJ-3301
三分写法似乎有问题, 可以去 Udebug 上看 Morass 的 \(666\) 个测试点的数据, 我的乱搞有很多比正解答案小, 但还是能在 SPOJ 和 POJ 过, 可见数据之水.
可以对正方形的角度模拟退火, 然后旋转坐标系将正方形变成平行与坐标轴的正方形, 这样我们只需计算旋转坐标系之后的所有点中 \(x/y\) 最大 / 最小的点就可以算出正方形的边长, 而旋转坐标系之后的点的坐标可以通过两角相加的 \(sin\) 和 \(cos\) 公式得到.
但很奇怪的一件事情是传统的模拟退火过不了样例......
我的乱搞写法同时借鉴了模拟退火和贪心, 其实就是模拟退火中 "如果 \(\Delta ans <0\), 则有 \(e^{\frac{\Delta ans}{T}}\) 的概率选择较不优的状态" 这个过程去掉, 每一次更优就选, 不优就不选, 具体为什么这样就对了我也不晓得 QAQ. 然后多做几次取平均值就可以得到答案.
- #include<iostream>
- #include<cstdio>
- #include<cctype>
- #include<algorithm>
- #include<iomanip>
- #include<cmath>
- #include<ctime>
- //This code is written by Itst
- using namespace std;
- #define ld long double
- const int times = 8;
- const ld pi = acos(-1) , eps = 1e-10 , delta = 0.985 , init = 5e5;
- int T , N , node[101][2];
- ld calc(ld mid){
- ld maxX = -1e18 , maxY = -1e18 , minX = 1e18 , minY = 1e18;
- ld Cos = cos(mid) , Sin = sin(mid);
- for(int i = 1 ; i <= N ; ++i){
- ld x = node[i][0] * Cos - node[i][1] * Sin , y = node[i][0] * Sin + node[i][1] * Cos;
- maxX = max(maxX , x); minX = min(minX , x);
- maxY = max(maxY , y); minY = min(minY , y);
- }
- return max(maxX - minX , maxY - minY);
- }
- int main(){
- #ifndef ONLINE_JUDGE
- freopen("in","r",stdin);
- freopen("out","w",stdout);
- #endif
- srand((unsigned)time(0));
- for(cin>> T ; T ; --T){
- cin>> N;
- for(int i = 1 ; i <= N ; ++i)
- cin>> node[i][0]>> node[i][1];
- ld all = 0;
- for(int i = 1 ; i <= times ; ++i){
- ld temp = init , cur = 0 , ans = calc(cur) * calc(cur);
- while(temp> eps){
- ld tmp = cur + (rand() * 2 - RAND_MAX) * temp / init / RAND_MAX * pi;
- ld ansT = calc(tmp) * calc(tmp);
- if(ans> ansT){
- ans = ansT;
- cur = tmp;
- }
- temp *= delta;
- }
- all += ans;
- }
- cout << fixed << setprecision(2) << all / times << endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2970661.html