月度归档:2017年08月

BZOJ 3680: 吊打XXX(模拟退火)

Description

gty又虐了一场比赛,被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身,但还是被人多势众的蒟蒻抓住了。蒟蒻们将
n个gty吊在n根绳子上,每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同,绳
结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标,由于他太弱了决定向你求助。
不计摩擦,不计能量损失,由于gty足够矮所以不会掉到地上。

Input

输入第一行为一个正整数n(1<=n<=10000),表示gty的数目。
接下来n行,每行三个整数xi,yi,wi,表示第i个gty的横坐标,纵坐标和重力。
对于20%的数据,gty排列成一条直线。
对于50%的数据,1<=n<=1000。
对于100%的数据,1<=n<=10000,-100000<=xi,yi<=100000

Output

输出1行两个浮点数(保留到小数点后3位),表示最终x的横、纵坐标。

Sample Input

3
0 0 1
0 2 1
1 1 1

Sample Output

0.577 1.000
看懂题目后发现貌似就是求个广义费马点。。然后学习了一下模拟退火,但是一直wa。。后来发现原来别人的起始点都设置成了一开始坐标的平均数,然后改过就过了,真是玄学,根本不懂为什么要这么写。。。

 

hdu 6166 Senior Pan(随机+最短路)

Problem Description
Senior Pan fails in his discrete math exam again. So he asks Master ZKC to give him graph theory problems everyday.
The task is simple : ZKC will give Pan a directed graph every time, and selects some nodes from that graph, you can calculate the minimum distance of every pair of nodes chosen in these nodes and now ZKC only cares about the minimum among them. That is still too hard for poor Pan, so he asks you for help.

 

Input
The first line contains one integer T, represents the number of Test Cases.1≤T≤5.Then T Test Cases, for each Test Cases, the first line contains two integers n,m representing the number of nodes and the number of edges.1≤n,m≤100000
Then m lines follow. Each line contains three integers xi,yi representing an edge, and vi representing its length.1≤xi,yi≤n,1≤vi≤100000
Then one line contains one integer K, the number of nodes that Master Dong selects out.1≤K≤n
The following line contains K unique integers ai, the nodes that Master Dong selects out.1≤ai≤n,ai!=aj

 

Output
For every Test Case, output one integer: the answer

 

Sample Input
1
5 6
1 2 1
2 3 3
3 1 3
2 5 1
2 4 2
4 3 1
3
1 3 5

 

Sample Output
Case #1: 2
因为我们要考虑的是集合内的最短路,相当于是个多源多汇的最短路。有一种非常神奇的随机的方式,就是把集合等分为两个集合,分别视为起点集合和终点集合。然后建个超级源汇跑dij就可以了,当然这样有1/4的概率跑出来正确答案,所以随机20次就可以了。
讲课的时候口胡了一下,现在写了写。。

 

BZOJ 1336&1337: [Balkan2002]Alien最小圆覆盖

Description

给出N个点,让你画一个最小的包含所有点的圆。

Input

先给出点的个数N,2<=N<=100000,再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)

Output

输出圆的半径,及圆心的坐标

Sample Input

6
8.0 9.0
4.0 7.5
1.0 2.0
5.1 8.7
9.0 2.0
4.5 1.0

Sample Output

5.00
5.00 5.00
两道一模一样的题,还放在一起是几个意思。。
为了给学弟们讲课学了一些奇怪的东西。。。
最小圆覆盖的一个随机做法,叫做随机增量法,把看似O(n^3)的东西实际上期望O(n),非常优秀而且好写。