【模拟退火】CF2C Commentator problem

简介: 笔记

题目描述


The Olympic Games in Bercouver are in full swing now. Here everyone has their own objectives: sportsmen compete for medals, and sport commentators compete for more convenient positions to give a running commentary. Today the main sport events take place at three round stadiums, and the commentator’s objective is to choose the best point of observation, that is to say the point from where all the three stadiums can be observed. As all the sport competitions are of the same importance, the stadiums should be observed at the same angle. If the number of points meeting the conditions is more than one, the point with the maximum angle of observation is prefered.


Would you, please, help the famous Berland commentator G. Berniev to find the best point of observation. It should be noted, that the stadiums do not hide each other, the commentator can easily see one stadium through the other.


输入格式


The input data consists of three lines, each of them describes the position of one stadium. The lines have the format x,y,r , where ( x,y ) are the coordinates of the stadium’s center  ( -10^3 <= x,y<=10^3 ) is its radius. All the numbers in the input data are integer, stadiums do not have common points, and their centers are not on the same line.


输出格式


Print the coordinates of the required point with five digits after the decimal point. If there is no answer meeting the conditions, the program shouldn’t print anything. The output data should be left blank.


具体思路

题意: 要求找到一个点,使得到三个圆的两切线张角相同,取最大张角的那个点输出,没有则不输出。


既然是模拟退火,那主要的就是两个部分:


估价函数

参数配置

那么对于评估函数的选定为:

1.png2.png

具体实现:

double evaluation(node &A) {
  double t[3], delta[3], res = 0;
  for (int i = 0; i < 3; i++)
    t[i] = distance(A, p[i]) / p[i].r;
  for (int i = 0; i < 3; i++) {
    delta[i] = t[i] - t[(i + 1) % 3];
    res += delta[i] * delta[i];
  }
  return res * 1e9;
}

3.png4.png

不过为了洛谷 AC 时刻的 🎉 还是很值得的。

5.png

那么附上全部代码:


代码实现

众所周知,rand()是个玄学

实验得: 1 / 2 {1 / 2}1/2 的概率通过

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
const double eps = 1e-14;
const double gradient = 0.996;
struct Point {
  double x, y, r;
} p[N];
struct node {
  double x, y;
} nowNode, ansNode;
double MINX = 1e9, MAXX = -1e9, MINY = 1e9, MAXY = 1e9;
double distance(node &A, Point &B) {
  return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
double evaluation(node &A) {
  double t[3], delta[3], res = 0;
  for (int i = 0; i < 3; i++)
    t[i] = distance(A, p[i]) / p[i].r;
  for (int i = 0; i < 3; i++) {
    delta[i] = t[i] - t[(i + 1) % 3];
    res += delta[i] * delta[i];
  }
  return res * 1e9;
}
node groop;
void SA() {
  nowNode = groop;
  double nowDelta = evaluation(nowNode);
  double T = 1e5;
  while(T > eps) {
    // double nowx = nowNode.x + (((rand() << 1) - RAND_MAX) > 0 ? -1 : 1) * T * rand() * 1.0 / RAND_MAX;
    // double nowy = nowNode.y + (((rand() << 1) - RAND_MAX) > 0 ? -1 : 1) * T * rand() * 1.0 / RAND_MAX;
    double nowx = nowNode.x + ((rand() << 1) - RAND_MAX) * T;
    double nowy = nowNode.y + ((rand() << 1) - RAND_MAX) * T;
    if(fabs(nowx) > 1000 || fabs(nowy) > 1000 || \
    nowx < MINX || nowx > MAXX || nowy < MINY || nowy > MAXY) {
      T *= gradient; 
      continue;
    }
    node tmpNode = {nowx, nowy};
    double tmpDelta = evaluation(tmpNode);
    double delta = tmpDelta - nowDelta;
    if(delta < 0) {
      nowNode = tmpNode;
      nowDelta = tmpDelta;
      ansNode = nowNode;
    } else if(exp(-delta / T) * RAND_MAX > 1.0 * rand()) nowNode = tmpNode, nowDelta = tmpDelta;
    T *= gradient;
  }
}
void solve() {
  srand(time(NULL));
  for (int i = 0; i < 3; i++) {
    cin >> p[i].x >> p[i].y >> p[i].r;
    nowNode.x += p[i].x / 3;
    nowNode.y += p[i].y / 3;
    MINX = min(MINX, p[i].x);
    MAXX = max(MAXX, p[i].x);
    MINY = min(MINY, p[i].y);
    MAXY = max(MAXY, p[i].y);
  }
  groop = nowNode;
  for(int i = 0; i < 300; i++) SA();
  if(evaluation(ansNode) < 1e-5) {
      printf("%.5lf %.5lf\n", \
      fabs(ansNode.x) < 1e-5 ? fabs(ansNode.x): ansNode.x, \
      fabs(ansNode.y) < 1e-5 ? fabs(ansNode.y): ansNode.y);
    }
}
int main() {
  solve();  
  return 0;
}
相关文章
【每日一题Day205】LC2441与对应负数同时存在的最大正整数 | 哈希表
【每日一题Day205】LC2441与对应负数同时存在的最大正整数 | 哈希表
84 1
力扣每日一题 6/1
力扣每日一题 6/1
96 3
《网上图书销售系统》功能需求 建立“顾客建立图书订单”的顺序图
《网上图书销售系统》功能需求 建立“顾客建立图书订单”的顺序图
256 0
|
Java
Java多重选择结构,超详细整理,适合新手入门
Java多重选择结构,超详细整理,适合新手入门
249 0
|
网络协议 Apache 应用服务中间件
easyUi datagrid 返回时间格式化操作
1.格式化返回的时间 {   field : 'endTime',   title : '轮播图片循环的结束时间',   width : 50,   align : 'center' //格式化时间操作 formatter:function(value,row,index){ ...
1222 0
|
算法 数据挖掘 数据库连接
2013百度校园招聘数据挖掘工程师
2013百度校园招聘数据挖掘工程师 一、简答题(30分)1、简述数据库操作的步骤(10分) 步骤:建立数据库连接、打开数据库连接、建立数据库命令、运行数据库命令、保存数据库命令、关闭数据库连接。 经萍萍提醒,了解到应该把preparedStatement预处理也考虑在数据库的操作步骤中。此外,对实时性要求不强时,可以使用数据库缓存。 2、TC
1829 0
|
10天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1211 5
|
9天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1173 87

热门文章

最新文章