【FJ互测】油滴扩展·改

2014年8月30日1,5660

【题目描述】

在大小A*B的paper中,将有N个圆形油滴。

已知第i个油滴信息如下: 中心位置:(Xi,Yi),开始扩散时间:Ti,扩散T时间后的面积: Ai*T

求paper被油滴完全覆盖的最短时间。

提示:保证有解

【输入】

一行三个非负整数A,B,N

接下来N行,每行四个非负整数Xi,Yi,Ti,Ai

【输出】

完全覆盖的最短时间,向上取整输出

【样例输入】

1000 1000 1

0 0 0 2

【样例输出】

3141593

【数据规模】

  • 对20%的数据,所有输入数字不超过10
  • 对另30%的数据,所有输入数字不超过100
  • 对所有数据,所有输入数字不超过1000

【题解】

 A:随机方法

1、 对于题意,我们发现“纸张被油滴完全覆盖”即为“纸张上一点最晚被覆盖”

2、 这是一个平面上的最优化问题,随意套用模拟退火等随机算法得解

我写了个随机起点的爬山。。。但是效果很差T T

std是秒杀啊。。。结果打开一看,区别似乎就在于他是上下左右随机走,我是随机一个方向。。。

接着一看。。。我随机的向量都是正的,不停往右上方走!!!!