「FJ互测」油滴扩展·改
「题目描述」
在大小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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<cmath> #include<algorithm> #include<map> #define inf 1000000000 #define ll long long using namespace std; const double pi=acos(-1.0); inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } double ans; int A,B,n; int x[1005],y[1005],a[1005],t[1005]; inline double getmn(double nowx,double nowy) { double mn=1e60; for(int i=1;i<=n;i++) { double tmp=((nowx-x[i])*(nowx-x[i])+(nowy-y[i])*(nowy-y[i]))*pi; tmp=tmp/a[i]+t[i]; mn=min(mn,tmp); } return mn; } int main() { //freopen("paper.in","r",stdin); //freopen("paper.out","w",stdout); srand(time(0)); A=read();B=read();n=read(); for(int i=1;i<=n;i++) { x[i]=read();y[i]=read();t[i]=read();a[i]=read(); } int T=10; while(T--) { double nowx=A*(rand()%1000/1000.0),nowy=B*(rand()%1000/1000.0),tx,ty,dis,now; double mx=getmn(nowx,nowy); double t=500; while(t>0.00001) { tx=rand()%10000-5000,ty=rand()%10000-5000,dis=sqrt(tx*tx+ty*ty); tx/=dis;ty/=dis; tx=nowx-tx*t;ty=nowy+ty*t; if(tx>A)tx=A;if(ty>B)ty=B; if(tx<0)tx=0;if(ty<0)ty=0; now=getmn(tx,ty); if(now>=mx){mx=now;nowx=tx;nowy=ty;} t*=0.985; } ans=max(ans,mx); } printf("%.0f",ceil(ans)); return 0; } |
std是秒杀啊。。。结果打开一看，区别似乎就在于他是上下左右随机走，我是随机一个方向。。。
接着一看。。。我随机的向量都是正的，不停往右上方走！！！！
Subscribe
计数器 9788862
OI 课件=>
OI 课件=>