HDU - 5017 Ellipsoid(模拟退火)
2024-09-07 18:43:09
题意
给一个三维椭球面,求球面上距离原点最近的点。输出这个距离。
题解
模拟退火。
把\(z = f(x, y)\)函数写出来,这样通过随机抖动\(x\)和\(y\)坐标就能求出\(z\)。
代码
//#include <bits/stdc++.h>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <iostream>
#define FOPI freopen("in.txt", "r", stdin)
#define FOPO freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
const int maxn = 100 + 5;
const double eps = 1e-3;
const int inf = 0x3f3f3f3f;
const double start_T = 10000;
struct Point
{
double x, y, z;
Point() {}
Point(double _x, double _y, double _z):x(_x), y(_y), z(_z) {}
};
double a, b, c, d, e, f;
int dx[] = {1, 1, 1, -1, -1, -1, 0, 0},
dy[] = {0, 1, -1, 0, 1, -1, -1, 1};
int n;
double dist(Point a)
{
return sqrt(a.x*a.x + a.y*a.y + a.z*a.z + 1e-8);
}
double getz(double x, double y)
{
double A = c, B = d*y + e*x, C = a*x*x + b*y*y + f*x*y - 1;
double delta = B*B - 4*A*C;
if (delta < -eps) return inf+1;
double z1 = (-B + sqrt(delta)) / 2 / A,
z2 = (-B - sqrt(delta)) / 2 / A;
return dist(Point(x, y, z1)) < dist(Point(x, y, z2)) ? z1 : z2;
}
double SA()
{
Point p(0, 0, getz(0, 0)), to;
double ans = dist(p), rate = 0.98, T = start_T;
while(T > eps)
{
double fx, fy, fz;
double tmp = inf;
for (int aim = 0; aim < 8; aim++)
{
fx = (p.x+1.0*dx[aim]/start_T*T);
fy = (p.y+1.0*dy[aim]/start_T*T);
//printf("%f\n", T);
fz = getz(fx, fy);
if (fz >= inf) continue;
double d = dist(Point(fx, fy, fz));
if (d < tmp)
{
tmp = d;
to = Point(fx, fy, fz);
}
}
if (tmp < ans)
{
ans = tmp;
p = to;
}
else if ((rand()%10000)/10000.0 < exp((ans-tmp)/ T * start_T))
{
ans = tmp;
p = to;
}
T *= rate;
}
return ans;
}
int main()
{
// FOPI;
srand(time(NULL));
while(~scanf("%lf%lf%lf%lf%lf%lf", &a, &b, &c, &d, &e, &f))
printf("%.7f\n", SA());
}
最新文章
- EXP/IMP 导出生产库表的指定数据到测试库一例
- 裸奔单片机GUI
- response 设置头的类型 (转)
- MVC应用程序结构与规划
- 慢牛系列三:React Native实践
- JAVA中的各种 哈希码(HashCode) 与 equals方法在HIBERNATE的实际应用[转载]
- 重写OnPaint事件对窗体重绘(显示gif动画) 实例2
- CSS 文本框里添加按钮的实现
- request.getParameterValues 出现 [Ljava.lang.String;@ 错误
- Silverlight Visifire控件应用去除图标的水印
- jmeter数据库连接配置
- hdu 2973";YAPTCHA";(威尔逊定理)
- mybatis中查询使用#{}和${}的区别
- wget下载指定URL下的特定属性文件
- Java流程控制语句
- 如何监控redis的cpu使用率
- TypeScript 之 模块
- 2018.11.01 bzoj4872: [Shoi2017]分手是祝愿(期望dp)
- 《Java多线程编程核心技术》——多线程与同步
- [吐槽]我为什么讨厌C++
热门文章
- 禁止Asp.Net WebService 的Test页面功能
- 分享一个WPF下日历控件(Calendar)的样式
- Centos7.5搭建ELK-6.5.0日志分析平台
- magento新增商品属性以及将属性加入Flat table
- 学习笔记:MDN的HTML
- win10 asp+access
- 运用CSS3媒体查询判断iPhoneX、iPhoneXR、iPhoneXS MAX及横竖屏
- Garmin APP开发之入门
- Apache Solr-6.0.1 (OpenLogic CentOS 7.2)
- String和string