相信这个特效你和你的朋友（或目标）必定玩过
当你发送一个便便的表情，对方假如扔一个炸弹表情，就会马上将这个便便炸开，完成满屏粑粑的“酷炫”画面。可谓是“臭味十足”，隔着屏幕都能感受到来自微信爸爸的满满歹意。
不清楚我们对这个互动规划怎么看，反正一恩当时是喜爱的不可，拉着朋友们就开端“炸”得不亦乐乎。
相同被虏获芳心的规划小哥哥在玩到尽兴后，突然灵感大发，连夜绘制出了规划稿，第二天就拉上产品和研制开端脑暴。
“微信炸感动我的一点是他满屏的规划，能够将用户激烈的情绪抒情出来；一起他能够与上一条表情进行绑缚，加强双方的互动性。”规划小哥哥声情并茂道。
“所以，让咱们的表情也‘互动’起来吧！”
这不，需求文档就来了：
改掉常见的emoji表情发送方法，替换为动态表情交互方法。即，
当用户发送或接收互动表情，表情会在屏幕上随机散布，展现一段时间后会消失。
用户能够频频点击并不停发送表情，因而屏幕上的表情是能够非常多且堆叠的，能够将用户爱情激烈抒情。
（暂用微信的谈天界面进行解释阐明，图1为原款式，图2是需求款式）
这需求一出，动态表情在屏幕上的散布计划便引起了研制内部火热讨论：当用户点击表情时，到底应该将表情放置在屏幕哪个方位比较好呢？
最直接的做法便是彻底随机方法：取0到屏幕宽度和高度中随机值，放置表情贴纸。但这么做的不确定因素太多，比方存在必定几率一切表情都集中在一个区域，布局边际化以及最差的堆叠问题。因而简单的随机算法对于用户的体验是无法接受的。
咱们开端探究新的计划：
由于现在点的选择依赖于较多元素，比方与屏幕已有点的间隔，与中心点间隔以及屏幕已有点的数目。因而终究决定选用点权随机的计划，依据上述元素决议计划出屏幕上可用点的优度，选取优度最高的刺进表情。
基本思路
维护对应屏幕像素的二维数组，数组元素代指新增图形时，图形中心取该点的优度。
选用懒加载的方法，即每次每次新增图形后，仅记录现有方块的方位，当需求一个点的优度时再核算。
遍历一切方块的方位，将图形内部的点优度全部减去 A ，将图形外部的点按到图形的曼哈顿间隔从 0 到 max (W,H)，映射，减 0 到 A * K2。
每次决议计划刺进方位时，随机取 K + n * K1 个点，取这些点中优度最高的点为刺进中心
A, K, K1, K2 四个常数可调整
一次选择的复杂度是 n * randT，n 是场上方块数， randT 是本次决议计划需求随机取多少个点。 从功率和 badcase来说，这个计划现在最优。
代码展现
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int screenW = 600;
const int screenH = 800;
const int kInnerCost = 1e5;
const double kOuterCof = .1;
const int kOutterCost = kInnerCost * kOuterCof;
class square
int x1;
int x2;
int y1;
int y2;
};
int lineDist(int x, int y, int p){
if (p < x) {
return x - p;
} else if (p > y) {
return p - y;
} else {
return 0;
}
}
int getVal(const square &elm, int px, int py){
int dx = lineDist(elm.x1, elm.x2, px);
int dy = lineDist(elm.y1, elm.y2, py);
int dist = dx + dy;
constexpr int maxDist = screenW + screenH;
return dist ? ( (maxDist - dist) * kOutterCost / maxDist ) : kInnerCost;
}
int getVal(const vector<square> &elmArr, int px, int py){
int rtn = 0;
for (auto elm:elmArr) {
rtn += getVal(elm, px, py);
}
return rtn;
}
int main(void){
int n;
cin >> n;
vector<square> elmArr;
for (int i=0; i<n; i++) {
square cur;
cin >> cur.x1 >> cur.x2 >> cur.y1 >> cur.y2;
elmArr.push_back(cur);
}
for (;;) {
int px,py;
cin >> px >> py;
cout << getVal(elmArr, px, py) << endl;
}
}
优化点
- 该算法最优解倾向边际。因而跟着随机值设置越多，得出来的点越倾向边际，因而随机值不能设置过多。
- 为了解决倾向边际的问题，每一个点在核算优度getVal需求加上与屏幕中心的间隔 * n * k3
作用演示
最终便是给我们演示一下最终的作用啦！
圆满完成任务，收工，下班！
