【BZOJ3680】吊打xxx [模拟退火]
2024-09-04 10:16:23
吊打XXX
Time Limit: 10 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]
Description
gty又虐了一场比赛,被虐的蒟蒻们决定吊打gty。
gty见大势不好机智的分出了n个分身,但还是被人多势众的蒟蒻抓住了。
蒟蒻们将n个gty吊在n根绳子上,每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。
吊好gty后蒟蒻们发现由于每个gty重力不同,绳结x在移动。
蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标,由于他太弱了决定向你求助。
不计摩擦,不计能量损失,由于gty足够矮所以不会掉到地上。
Input
输入第一行为一个正整数n,表示gty的数目。
接下来n行,每行三个整数xi,yi,wi,表示第i个gty的横坐标,纵坐标和重力。
对于20%的数据,gty排列成一条直线。
Output
输出1行两个浮点数(保留到小数点后3位),表示最终x的横、纵坐标。
Sample Input
3
0 0 1
0 2 1
1 1 1
0 0 1
0 2 1
1 1 1
Sample Output
0.577 1.000
HINT
对于50%的数据,1<=n<=1000。
对于100%的数据,1<=n<=10000,-100000<=xi,yi<=100000
Main idea
求一个坐标,使得整个坐标到其余点的dist*val最小。
Solution
我们看到这种数据,显然使用模拟退火即可。
Code
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long s64; const int ONE = ;
const int INF = ; int n;
double Ans_min = 1.0*1e18;
double T; struct power
{
double x,y;
double val;
}a[ONE],Now,Ans,A; int get()
{
int res=,Q=; char c;
while( (c=getchar())< || c>)
if(c=='-')Q=-;
if(Q) res=c-;
while((c=getchar())>= && c<=)
res=res*+c-;
return res*Q;
} double dist(power a,power b)
{
return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
} double Judge(power Now)
{
double res=;
for(int i=;i<=n;i++)
res+= a[i].val * dist(Now,a[i]);
if(res < Ans_min) Ans_min = res, Ans = Now;
return res;
} double Random() {return (double)rand()/RAND_MAX;}
void SA(double T)
{
Now = Ans;
while(T > 0.001)
{
A.x = Now.x + T*(Random() * -);
A.y = Now.y + T*(Random() * -);
double dE = Judge(Now) - Judge(A);
if(dE > || Random() <= exp(dE/T))
Now = A;
T *= 0.98;
}
for(int i=; i<=; i++)
{
A.x = Ans.x + T*(Random() * - );
A.y = Ans.y + T*(Random() * - );
Judge(A);
}
} int main()
{
n=get();
for(int i=;i<=n;i++)
{
a[i].x=get(); a[i].y=get(); a[i].val=get();
Ans.x += a[i].x; Ans.y += a[i].y;
}
Ans.x/=n; Ans.y/=n; SA(); printf("%.3lf %.3lf",Ans.x,Ans.y);
}
最新文章
- Spark调度管理(读书笔记)
- Linux下Awk详解(转载)
- PHP 基本语法,字符串处理,正则
- 简介AngularJS中使用factory和service的方法
- 《Linux内核设计与实现》课本第一章&;第二章学习笔记
- MvvmLight框架使用入门(一)
- eclipse+maven 无法编译
- MySQL Partition分区扫盲
- eclipse内使用tomcat项目究竟被部署到了哪里
- Java基础知识强化之集合框架笔记64:Map集合之ArrayList嵌套HashMap
- BZOJ 1052 覆盖问题
- bzoj3531——树链剖分+动态开点线段树
- 机器学习基础—集成学习Bagging 和 Boosting
- 二十、Hadoop学记笔记————Hive On Hbase
- jquery AJAX数据传输路径写法~
- ABP中mapping中忽略属性
- Nginx与ftp服务器
- 浅析C/C++中的switch/case陷阱
- Windows解压安装mysql 5.7.24,并部署多个mysql服务
- std::nothrow 的使用心得
热门文章
- kettle 遇到 解决Incorrect integer value: &#39;&#39; for column &#39;id&#39; at row 1 完美解决-费元星
- Linux用户态程序计时方式详解[转]
- 在Kotlin上怎样用Mockito2 mock final 类(KAD 23)
- 接口测试工具postman(二)创建新项目
- 教程|要想Hadoop能够运行Python程序,就要会MRJob
- ZooKeeper完全分布式安装与配置
- su: Authentication failure
- QR码与DM码的区别
- picker组件,mode=date,苹果机年份从1开始
- Daily Scrum02 12.01