w********2
发帖数: 16371 | 1 发现bullmaster的原帖被删除了，正好有备份，再转过来。原来标题里的一些字删除了。
【 以下文字转载自 Apple_II 俱乐部 】
发信人: wavelets02 (波士顿), 信区: Apple_II
标 题: 被隔壁ablution那个傻叉封了，在这里说说圆角矩形 (转载)
发信站: BBS 未名空间站 (Sat Feb 16 13:48:28 2013, 美东)
【 以下文字转载自 Apple 讨论区 】
发信人: bullmaster (master), 信区: Apple
标 题: 被隔壁ablution那个傻叉封了，在这里说说圆角矩形
发信站: BBS 未名空间站 (Sat Feb 16 13:12:06 2013, 美东)
Fuck，圆角矩形是Apple Design, and there is a history for that.
圆角矩形要追溯到30年前的Apple Lisa，Steve Jobs坚持苹果图形界面上的矩形必须是
圆角而不是尖角。 Steve wanted Apple computer to model objects in reality... 阅读全帖 |
|
d*****0
发帖数: 68029 | 2 【 以下文字转载自 Apple 讨论区 】
发信人: bullmaster (master), 信区: Apple
标 题: 被隔壁ablution那个傻叉封了，在这里说说圆角矩形
发信站: BBS 未名空间站 (Sat Feb 16 13:12:06 2013, 美东)
Fuck，圆角矩形是Apple Design, and there is a history for that.
圆角矩形要追溯到30年前的Apple Lisa，Steve Jobs坚持苹果图形界面上的矩形必须是
圆角而不是尖角。 Steve wanted Apple computer to model objects in reality，so
people will not be afraid of computers.
但当时的硬件条件下在屏幕上画圆是件很慢的事情，因为要计算平方。 Apple
engineer Bill Atkinson 发明了只用相邻奇数之和算平方的算法，比如1+3=4, 1+3+5=
9, etc. 所以当时只有苹果的电脑才可以在屏幕上快速画圆弧。 圆角矩形就好像6色
的彩色苹果标志... 阅读全帖 |
|
d********u
发帖数: 5383 | 3 【 以下文字转载自 Apple 讨论区 】
发信人: bullmaster (master), 信区: Apple
标 题: 被隔壁ablution那个傻叉封了，在这里说说圆角矩形
发信站: BBS 未名空间站 (Sat Feb 16 13:12:06 2013, 美东)
Fuck，圆角矩形是Apple Design, and there is a history for that.
圆角矩形要追溯到30年前的Apple Lisa，Steve Jobs坚持苹果图形界面上的矩形必须是
圆角而不是尖角。 Steve wanted Apple computer to model objects in reality，so
people will not be afraid of computers.
但当时的硬件条件下在屏幕上画圆是件很慢的事情，因为要计算平方。 Apple
engineer Bill Atkinson 发明了只用相邻奇数之和算平方的算法，比如1+3=4, 1+3+5=
9, etc. 所以当时只有苹果的电脑才可以在屏幕上快速画圆弧。 圆角矩形就好像6色
的彩色苹果标志... 阅读全帖 |
|
m**q
发帖数: 189 | 4 思路大概是这样的
因为所有矩形的底边都在x轴上，把每个矩形的左上角和右上角的坐标记录到
一个数组中，每个元素是 pair, int start>，每个矩形
在数组中有两个元素，代表左右两条边，start为1表示开始，为0表示结束。
比如，一个矩形的x轴开始坐标为x1，结束坐标为x2，高为y，则在数组中它
对应的两个元素是 <, 1>, <, 0>
可知n个矩阵生成的数组中有2n个元素，然后sort数组，复杂度O(nlgn)
然后用sweepling line algorithm，扫描数组，用一个BST记录当前
overlapping的所有矩形。
遇到矩形的左边时(start==1)，判断边的高度（即当前y值）是否大于BST中
的最大高度，大于则记录两个点，（当前x值，BST中最大高度），
(当前x值，当前y值)。把当前y值放入BST
遇到矩形的右边时(start==0),把当前y值从BST中删除，如果BST有相同值只删除
一个。判断边的高度（即当前y值）是否大于当前BST中的最大高度，大于则
记录两个点，（当前x值，当前y值... 阅读全帖 |
|
d*******l
发帖数: 338 | 5 矩形那个题，这里只说通过overlap形成一个不规则图形的若干个矩形。假设有n个，那
这n个矩形最多有2n条垂直的边。这2n条垂直的边所在的直线和最后图形的交点处才可
能形成分界点。把这些直线按坐标排序，然后用这些直线把原来的那些矩形分成更小的
矩形，把小矩形排序。然后确定每个小区间上的高度，最后扫描一下这些小区间，前后
出现高度差的就构成一个分界点。应该可以做到O(nlogn)。
(i |
|
d*******l
发帖数: 338 | 6 所有矩形有一条边都是共线的。2n条垂直的边可以把水平方向划分成若干个单位区间，
把所有矩形分割成在单位区间上的小矩形，每个区间上取最高的那个小矩形就可以。相
互覆盖的情况已经蕴涵在里面了，不用特殊考虑。所有矩形的一条边共线是很重要的条
件，没有这个条件这么弄就不行。 |
|
h**6
发帖数: 4160 | 7 一个矩阵，所有元素都是0或者1，要在这个矩阵中寻找面积最大的
1)完全由1组成的矩形，正方形
2)四边由1组成的矩形，正方形
3)四个顶点是1的矩形，正方形
第一题我会，矩形和正方形都可以由动态规划求出。后面2, 3两题怎么求，有人有思路
吗？最低复杂度是多少呢？ |
|
j**l
发帖数: 2911 | 8 考虑直方图的每个元素（每根柱子)，以它为高度的最大矩形，宽度可以向左右扩展。
所以问题就转换为怎么确定左右边界。
我们使用了一个栈，从左到右每根柱子依次入栈。
情形一：如果栈不空并且当前将要入栈的柱子比栈顶的柱子低，则有：
1. 栈顶柱子的右边界完全确定，其对应的局部最大矩形面积可求(下面说明了左边界在
它入栈时已确定)。更新全局最大矩形面积后，栈顶柱子可以依次出栈，直到当前的栈
顶柱子比当前要入栈的柱子低或者栈变为空栈。
2. 连续的出栈操作使得当前的栈顶柱子比当前要入栈的柱子低或者栈变为空栈, 这时
候，当前要入栈的柱子的左边界也确定,可以入栈。
情形二：如果栈为空或者当前要入栈的柱子比栈顶柱子高，则无出栈操作，且当前要入
栈的柱子的左边界确定。
总结：
1. 每个入栈操作, 如果入栈柱子低于栈顶柱子,则它确定了栈中比要入栈柱子高的那些
柱子的右边界,可以对它们执行出栈操作。出栈的过程伴随着矩形面积的计算。
2. 每个入栈操作，不论是否引起出栈操作,我们都可以确定当前要入栈柱子的左边界。
3. 每次入栈后,栈内所剩柱子一定保持高度单调非递减的顺序。
4. 可令最后一根柱子高度为-1 |
|
d*******l
发帖数: 338 | 9 先明确一下，这题要求的是最后的不规则图形的边界点，这个理解上没有异议吧？你的
例子中就是A的左下、左上，AB的那个交点，以及B的左上、右上、右下。这个不画出来
要讲清楚确实有点难，你这个图中，B的一条边把A分成了两个矩形，A的一条边（所在
直线）也把B分成了两个矩形，所以我们有4个单位区间上的矩形，第二个区间上有两个
小矩形，一个来自A，一个来自B，我们取高的那个。然后对于每两个相邻的单位区间，
只要有高度差就有两个边界点，否则就没有。 |
|
z*j
发帖数: 42 | 10 如果矩形，能否记录矩形的长和宽（ｘ，ｙ），然后再ｘ，ｙ 分别 1+min{B(i-1,j)
, B(i,j-1), B(i-1,j-1)}？ |
|
l*********y
发帖数: 142 | 11 还有牛人follow这个帖子吗？
到现在我只有1) 的正方形有最优解,楼上讨论的1)的矩形对吗?
110
010
111
111
右下角Entry (3,2) 的最大面积矩形是2*3 = 6. 怎么求出的?
2) 和 3)完全没懂楼上的讨论. |
|
P**********c
发帖数: 3417 | 12 后来大家有一致结论吗？
9.N个矩形，所有矩形都有一条边在同一条直线上，他们相互可能有overlap，找出最后
得到的这个不规则图形的所有边界点
还有那个score(i)的题
8.给N个元素，第i个元素有一个大于0的score(i)，要求随机选出k个，每个元素可以被
选择任意多次，但保证被选择的概率要和score(i)成比例
有人说算score(i)/sum(score(i)), 但是细节上的实现，
是不是先选一个random在(1,n)的数i，然后生成一个(0,1)内的数，看是否小于score(i
)/sum(score(i))来决定是否取i, 如果取了i呢。i的score要调整吗？如何调整？ |
|
s*****y
发帖数: 897 | 13 但是某些矩形的顶点或者边可能被另一个矩形覆盖了,这种情况怎么办啊? |
|
d*******l
发帖数: 338 | 14 上面代码中矩形的表示方式是左下和右上顶点的坐标。所有矩形的左下顶点必须都是共
线的。测试的时候这样就可以：
int main()
{
FindVertex fv;
fv.add(1, 0, 5, 2);
fv.add(2, 0, 6, 3);
fv.add(4, 0, 8, 4);
fv.solve();
return 0;
}
最后顺时针输出所有边界上的顶点。 |
|
p*****u
发帖数: 310 | 15 谁说所有矩形的左下顶点必须都是共线的？难道不能右上顶点和其他矩形的左下顶点共
线？ |
|
|
l*********m
发帖数: 16971 | 17 【 以下文字转载自 Apple 讨论区 】
发信人: lovefreedom (happy), 信区: Apple
标 题: 圆角矩形专利成为苹果公司的杀手锏
发信站: BBS 未名空间站 (Wed Aug 29 12:46:06 2012, 美东)
这个专利让大家看清了苹果的形象，这哪是高科技公司啊，PhD们搞了数年研究还不如
画个圆角矩形 |
|
l*********m
发帖数: 16971 | 18 【 以下文字转载自 Apple 讨论区 】
发信人: lovefreedom (happy), 信区: Apple
标 题: 圆角矩形专利成为苹果公司的杀手锏
发信站: BBS 未名空间站 (Wed Aug 29 12:46:06 2012, 美东)
这个专利让大家看清了苹果的形象，这哪是高科技公司啊，PhD们搞了数年研究还不如
画个圆角矩形 |
|
z****e
发帖数: 54598 | 19 【 以下文字转载自 PDA 讨论区 】
发信人: bullmaster (master), 信区: PDA
标 题: 今天再说说圆角矩形
发信站: BBS 未名空间站 (Thu Feb 28 21:11:27 2013, 美东)
这里微软的几个小摧奔反复纠缠圆角矩形，wiki上自己去看，有问题去问Walter
Isaacson和Andy Hertzfeld，不要来跟我纠缠，上次谁删的我的帖子谁死全家哦。
http://en.wikipedia.org/wiki/Bill_Atkinson
我发现国内出来的屌丝软工们对硅谷事情一点常识都没有。 微软的尤其傻叉。上次那
个LeftEye不知道Office先有的Mac版再有的Windows，真是可笑。
Bill Atkinson大隐隐于世，个人电脑工业还史前混沌一片的时候，人的软件开创了无
数先河。微软这几个不入流的软工对人也敢说三道四。 就好像牛家村前的几个金兵遇
见洪七公，有眼不认识你们做软工的祖宗。 真是TMD可笑。 |
|
s******g
发帖数: 15854 | 20 业余天文爱好者们日前在火星表面观测到一个尖锐的突起物，这个物体看上去呈现几乎
完美的矩形直立结构
科幻电影《2001太空奥德赛》的场景：外星人在地球上树立的方形石碑
北京时间4月23日消息，据美国太空网报道，业余天文爱好者们日前宣称他们在火星表
面观测到一个尖锐的突起物。这个物体看上去呈现几乎完美的矩形直立结构。爱好者们
在美国宇航局拍摄的火星表面高分辨率图像中找到了这个物体，看上去它和经典科幻影
片《2001太空奥德赛》中在月球和火星上发现的那种外星文明建造的方形石碑非常相似。
这个奇特的物体最早是在数年前被美国宇航局在轨运行的火星勘测轨道器(MRO)搭载的
高分辨率成像科学实验相机(HiRISE)拍摄的图像中被发现的，随后这个物体在互联网上
吸引了越来越多网民的关注。人们不禁浮想联翩：这是外星人出于某种神秘的原因而在
此修建的吗？更加诡异的是，为什么它的外形和电影《2001太空奥德赛》中所描绘的情
景那么相似？这究竟是人工建造的还是自然作用的产物？
美国亚利桑那州立大学火星空间飞行中心研究员乔纳森·希尔(Jonathon Hill)负责火
星探测任务规划，也曾经处理过很多火星探测器... 阅读全帖 |
|
l*********m
发帖数: 16971 | 21 【 以下文字转载自 Apple 讨论区 】
发信人: lovefreedom (happy), 信区: Apple
标 题: 圆角矩形专利成为苹果公司的杀手锏
发信站: BBS 未名空间站 (Wed Aug 29 12:46:06 2012, 美东)
这个专利让大家看清了苹果的形象，这哪是高科技公司啊，PhD们搞了数年研究还不如
画个圆角矩形 |
|
z****e
发帖数: 54598 | 22 【 以下文字转载自 PDA 讨论区 】
发信人: bullmaster (master), 信区: PDA
标 题: 今天再说说圆角矩形
发信站: BBS 未名空间站 (Thu Feb 28 21:11:27 2013, 美东)
这里微软的几个小摧奔反复纠缠圆角矩形，wiki上自己去看，有问题去问Walter
Isaacson和Andy Hertzfeld，不要来跟我纠缠，上次谁删的我的帖子谁死全家哦。
http://en.wikipedia.org/wiki/Bill_Atkinson
我发现国内出来的屌丝软工们对硅谷事情一点常识都没有。 微软的尤其傻叉。上次那
个LeftEye不知道Office先有的Mac版再有的Windows，真是可笑。
Bill Atkinson大隐隐于世，个人电脑工业还史前混沌一片的时候，人的软件开创了无
数先河。微软这几个不入流的软工对人也敢说三道四。 就好像牛家村前的几个金兵遇
见洪七公，有眼不认识你们做软工的祖宗。 真是TMD可笑。 |
|
t**********t
发帖数: 12071 | 23 假设这个区域是连通的，边界是连续的。矩形们不相交。所有矩形的长边是互相平行的。
有没有相关的现成的理论阿？ |
|
t**********t
发帖数: 12071 | 24 给大哥磕头了。呵呵。
可是我想用尽可能少的矩形。或者说，为了覆盖(1-\epsilon)的区域的面积，我最少得
用多少个矩形？ |
|
t******t
发帖数: 15246 | 25 环球网记者朱盈库报道，据英国路透社7月20日报道，随菲律宾议员登陆南沙中业岛的
菲律宾西部司令部司令萨班中将宣称，菲律宾海军近日在南海一个无人居住的环礁附近
清除了一座“闯入菲律宾领海”的矩形金属平台。
萨班7月20日表示，菲律宾海军一艘舰船11日从巴拉望以西约110公里的仙宾礁(菲称“
萨拜纳礁”)拖走了这座金属平台。这座平台于10日被菲律宾一架巡逻机发现。
萨班称，依据《南海各方行为宣言》条款，这座平台为“非法建筑物”，然而它上面“
没有任何记号”，因此很难知晓其拥有者。他还表示，因为平台出现在菲律宾“专属经
济区”范围内，因此它“闯入了菲律宾领土”。
htt p://news.ifeng.com/mainland/special/nanhaizhengduan/content-3/detail_
2011_07/20/7826466_0.shtml |
|
|
l*******r
发帖数: 511 | 27 equal就skip呗
这个题的关键是理解最大的矩形肯定要以某个unit为高。。而这个unit能extend到多左
边多
右边则是由stack里的比它低的那个和将要让它pop的那个决定的
one question here, if there are bars Bi, Bi-1, Bi-2 in the stack top that
are higher than current bar Bj
if you remove (Bi, Bi-1, Bi-2), and then push Bj to stack, how do you know
how many bars higher than Bj?
Also, if you meet a bar Bj height equals to the stack top Bi, what will you
do?
Anybody please share if you get clear ideas about this, thanks. |
|
g*****u
发帖数: 298 | 28 能否用这个例子讲一下你的算法如何找出3的最大矩形
0 1 1 1
1 1 1 0
0 1 0 0 |
|
d*******l
发帖数: 338 | 29 这个不能凭空猜测，面试的时候肯定要提问澄清。所有矩形都在一条直线一侧好处理些
，如果在两侧，方法还可以是类似的，但会麻烦些 |
|
m**q
发帖数: 189 | 30 这个思路我当场肯定想不到...
不过想了想，所有小矩形最多可能有O(n^2)个，
对它们进行排序需要O(n^2*lgn)
如果用sweepling line algorithm，用一个set记录
过程中的端点，应该可以O(nlgn) |
|
g*****i
发帖数: 2162 | 31 矩形题讲思路就可以了,思路对面试官会引导你的. |
|
k**********4
发帖数: 1317 | 32 五军之战看了普通版，还想去感受下imax，在附近搜到几家影院有球形还有矩形，有
hdr
还有70mm胶片，哪种比较好呢？求建议！
★ 发自iPhone App: ChineseWeb 8.7
★ 发自iPhone App: ChineseWeb 8.7 |
|
W**********4
发帖数: 322 | 33 【 以下文字转载自 Apple 讨论区 】
发信人: wwwhu (fc), 信区: Apple
标 题: Re: 在这里说说圆角矩形 (转载)
发信站: BBS 未名空间站 (Mon Feb 25 20:11:35 2013, 美东)
在Apple engineer Bill Atkinson之前，计算数学的芽都还萌发，虽然有那么多f(x),f
'(x)计算的东西。苹果的一个工程师，把人类从数字的迷茫和蒙昧中引了出来。 |
|
l******s
发帖数: 154 | 34 有一个老掉牙的寓言：富翁到美丽的海滨城市度假，在海边沙滩一边休闲，一边教
导身边晒太阳的渔夫说，“你不应该这么不自强，你应该努力工作，赚更多的钱，然后
像我一样，有条件来此度假。”渔夫懒洋洋地回答说，“我现在已经天天在这里度假了
。”
还有个笑话说，记者问山里的放羊娃为何放羊，回答说攒钱娶媳妇生娃；问生了娃
让娃做什么，回答说放羊。
这两个故事，很耐嚼。活着的目的是什么？活着的过程和目的相比，哪个更重要？
如果无法兼得，做何选择？
有首歌说，想去桂林，可是有时间的时候没钱，有钱后又没了时间。
偶然吗？悖论吗？
不是偶然。有得必有失，有舍才有得，鱼与熊掌难兼得，这其中蕴含深意。
不是悖论。万法归宗，不同表象之下，是同一本质。
生活中常看到，忙的人忙得不可开交，生活节奏像开机关枪，工作时上厕所都要匆
匆去匆匆出，下班逛逛公园、晒晒太阳的时间都要挤；而闲的人一步三摇三步九晃，整
日无所事事，逛着公园心不在焉，晒着太阳两眼发呆。
忙人羡慕闲人的大把的时间，闲人嫉妒忙人的乐观充实。
一般来说，忙的人是重要的人，至少是被别人需要着的人，有个人价值，在忙碌中
实现价值，很多价值与金钱无关。而闲的人，... 阅读全帖 |
|
a***y
发帖数: 19743 | 35 为什么NextStep里面都是没有圆角的矩形呢？
因为当时Apple有这个专利，Jobs就避开了？
了。 |
|
i********y
发帖数: 346 | 36 偶用surf函数画曲面，可是由于该曲面的平面投影不是矩形，所以一些边缘元素必须设
成NaN,然而这么一来用surf或者mesh画出来的曲面边缘是棱棱角角的，不是封闭的，请
教如何解决这个问题，谢谢了。 |
|
m*********s
发帖数: 368 | 37 ☆─────────────────────────────────────☆
okla (IP~IC~IQ卡，统统告诉我密码) 于 (Thu Aug 25 16:26:11 2005) 提到:
在Ahlfors书上p238-p241，他使用Schwartz-Christoffel变换F(w)将上半平面映到一个矩
形，
并且-1/k, -1, 1, 1/k (其中0
其中K, K'是正常数。
但是我怎么得到的不是矩形，而是一个关于z=0对称的图形啊？
而且根据这一节习题3(p241)，F(w)的逆变换f(z)是奇函数，所以F(w)也是奇函数，
从而-1/k和1/k应该映到关于z=0对称的点才对。
详细的说明(及图示)见
http://anywhereenterprises.com:80/1/1/a?a=dF&p=pQZsOWrl1Y5iy7POAArl1OAArl1dQX
☆─────────────────────────────────────☆
TheMatrix (TheMatrix) 于 |
|
b*******i
发帖数: 20 | 38 好像很麻烦啊，匆匆想到下面三种解法，抛砖引玉。
1. 暴力求解，时间复杂度至少是O(S^3)，我不确定
找到下面各种矩形
R0 = 相交至少0次的矩形 （就是原来的矩形）
R1 = 相交至少1次的矩形，(就是上一步R0的交集，复杂度O(S^2), 如果为空，就不要
往下算了)
R2 = 相交至少2次的矩形 (就是上一步R1的交集)
...
R(S-1) = 相交至少S-1次的矩形
结果是R0-R1+...
2. 分割矩形， 时间复杂度至少是O(S^2)，我不确定
从1个矩形开始，加入第2个矩形后，如果有相交，记录他们分割的小矩形。
再加入第3个矩形，跟前面的小矩形如果有相交，记录他们分割的小矩形。
...
结果是所有分割后小矩形的面积之和。
3. 另外坐标是整数，离散化方法。 |
|
i******s
发帖数: 301 | 39 可以这么做，不过既然是puzzle，interviewer希望你能推导出答案，这个可以先从简
单情况开始推导。
如果board是1*N的，那么显然有N个1*1的矩形，N-1个1*2的矩形，。。。1个1*N的矩形
，所以1*N情况下，一共有N + (N-1) + (N-2) + .. + 1 = N(N+1)/ 2个矩形。
再设想如果是2*N的board，可以分成两个1*N的board，设1*N的board总共有X个矩形，
那么2*N至少有2X个矩形(两个1*N board未连接)，如果把两个2*N的board连接起来，那
么会多出2*1, 2*2, 2*3 ... 2*N的矩形，数量如同1*N board的数法，一共有 X个。所
以2*N board 一共包含3X个矩形，X为1*N board 所包含的矩形数。
如果是M*N的board, 我们把他拆解为M个1*N board, 那么至少有MX个(每个1*N board
都不相连)，现在我们可以选择将M个1×N board中任意两个相连来寻找所有2*1, 2*2,
... 2*N的矩形，一共有M-1种组合。如果考虑选取任意三个1*N b... 阅读全帖 |
|
c****t
发帖数: 19049 | 40 “是的。‘自然选择’号的聚变燃料已经在折返容量以下，必须补充燃料后才能返回太
阳系，而追击舰队也没有足够的燃料给我们补充。那六艘战舰的吨位都只有‘自然选择
’号的一半，追击中曾加速到百分之五光速，然后又经历了同样强度的减速，燃料都刚
够自己折
返。所以‘自然选择’号上的人员只能搭乘追击舰队返回，以后会有飞船携带足够的燃
料追
上‘自然选择’号，使其返回太阳系，但这需要很长时间，我们在离开前尽可能减速，
就能
缩短这段时间。”
“东方，不要减速。”
“为什么？”
“减速将耗尽‘自然选择’号的剩余燃料，我们不能成为一艘没有能量的飞船，谁也不
知道将会发生什么，作为舰长你应该想到这点。”
“能发生什么？未来已经很清晰了，战争将结束，人类将胜利，而你被证明完全错了！”
章北海对激动的东方笑了笑，似乎是想平息她的情绪，这时，他看她的眼光变得从未有
过的柔和，这使得东方的心绪一阵波动。尽管她一直认为章北海的失败主义思想不可思
议，
一直怀疑他的叛逃有别的目的，甚至怀疑他精神有问题，但不知为何，仍对他生出一种
依恋
感。她在很小的时候就离开了父亲——当然对这个时代的孩子来说这是正常的事，父爱
已经
... 阅读全帖 |
|
g****o
发帖数: 547 | 41 第二题我又想了个解法，不知道有没有人来讨论下还有没有更好的解:)
所求矩形的上边要么贴着边界，要么贴着某个已有矩形的下边
所求矩形的下边要么贴着边界，要么贴着某个已有矩形的上边
所求矩形的左边要么贴着边界，要么贴着某个已有矩形的右边
所求矩形的右边要么贴着边界，要么贴着某个已有矩形的左边
因为N只有100,这样所有所求的矩形不超过1e8种可能
用brute-force依次检验是否和现有矩形重叠,并求最大，最终时间1e10
在给定限制条件下，比刚才的1e12要好一点,也差不多达到了可接受的计算时间
C++花几分钟到十几分钟吧 |
|
r**a
发帖数: 31 | 42 你复杂度是不是算错了，新窗口的w,h是给定的，窗口的位置有O(N^2)种可能，每次计
算重叠是O(N)，总复杂度不过O(N^3) 1e6
第二题我又想了个解法，不知道有没有人来讨论下还有没有更好的解:)
所求矩形的上边要么贴着边界，要么贴着某个已有矩形的下边
所求矩形的下边要么贴着边界，要么贴着某个已有矩形的上边
所求矩形的左边要么贴着边界，要么贴着某个已有矩形的右边
所求矩形的右边要么贴着边界，要么贴着某个已有矩形的左边
因为N只有100,这样所有所求的矩形不超过1e8种可能
用brute-force依次检验是否和现有矩形重叠,并求最大，最终时间1e10
在给定限制条件下，比刚才的1e12要好一点,也差不多达到了可接受的计算时间
C++花几分钟到十几分钟吧 |
|
w*******s
发帖数: 138 | 43 给出若干矩形，矩形可以从大到小重叠摆放，但是放在上面的矩形必须能够完全放入下
面的矩形中，每个矩形上至多只能放另外一个矩形，摆放的时候矩形的边必须相互垂直
或平行（不可任意旋转），求最优摆放方案使得总占地面积最小。
面试应该不会考这么偏的。 |
|
r***u
发帖数: 1272 | 44 1. 两幅图片同时动作
PowerPoint的动画效果比较多，但图片只能一幅一幅地动作。如果你有两幅图片要一左
一右或一上一下地向中间同时动作，可就麻烦了。其实办法还是有的，先安置好两幅图
片的位置，选中它们，将之组合起来，成为"一张图片"。接下来将之动画效果设置为"
左右向中间收缩"，现在请看一看，是不是两幅图片同时动作了？
2. 滚动文本框的制作
右击工具栏打开"控件工具箱",再点击文本框,而后从"属性"里面把滚动条打开,在TEXT
里面输入文本框的内容.(完成)还可以通过"其他控件"中的SHOCKWAVE FLASH OBJECT 实
现PPT中加入FLASH。
3. 轻松隐藏部分幻灯片
对于制作好的powerpoint幻灯片，如果你希望其中的部分幻灯片在放映时不显示出来，
我们可以将它隐藏。方法是：在普通视图下，在左侧的窗口中，按 Ctrl，分别点击要
隐藏的幻灯片，点击鼠标右键弹出菜单选“隐藏幻灯片”。如果想取消隐藏，只要选中
相应的幻灯片，再进行一次上面的操作即可。
4.在PPT演示文稿内复制幻灯片
要复制演示文稿中的幻灯片，请先在普通视图的“大纲”或“幻灯片”选项中，选择... 阅读全帖 |
|
发帖数: 1 | 45 天文学家无论如何都不可能找到通往天堂的阶梯，但是美国国家航天局的哈勃望远镜却
仿佛让人类看到了这样的盛景，它拍摄的图片显示在一颗“垂死”的星体周围围绕着梯
状结构的星云。
哈勃望远镜拍摄的一张图片让科学家对银河系中最不同寻常的，编号为HD44179的星云
有了新的认识。通常科学家将这类星云称为红矩形星云，因为从地面天文望远镜看去，
它呈现出矩形结构，颜色为红色。但由于大气层的遮掩，科学家从地面天文望远镜对这
一星云进行观测受到了诸多的限制，而这次哈勃望远镜拍摄的图片则让科学家们看到了
该星云此前不为人知的一些新特性。
0926
哈勃望远镜拍摄的图片显示，红矩形星云并非矩形，实际上它呈现出一种X形的结构，
科学家认为这种现象是由于构成星体内核的气体和尘埃挥发所致。挥发出来的气体向星
体相反的两个方向喷射，最终我们就看到了这种类似于将两个冰淇淋尖端接在一起的X
形结构。更令人关注的是，在星体周围呈现出一种阶梯状的结构，使得整个星云看起来
就象一张蜘蛛网，这种形状在已知的星云中绝无仅有。
该星云中心的星体寿命同太阳差不多，不过它已经走到了生命的终点。这颗恒星的外层
物质开始向外界挥发，从而形... 阅读全帖 |
|
d******a
发帖数: 32122 | 46 第一章 盗洞中挖出遗尸 刑侦队赶赴现场
一四年五月八号下午一点钟左右，荆南市公安局刑侦队值班室响起了急促的电话铃
声，值班员是柳彬。
电话的内容是：省考古队在二龙山南唐古墓的挖掘现场发现了一具尸体。这具尸体
是在盗洞里面发现的，陵寝的挖掘工作还没有推进到墓室——这具尸体显然是盗墓贼的
尸体——尸体已经腐烂。
欧阳平看完电话记录以后，临时改变了工作计划，他本来是准备到火车站去接刘大
羽的。刘大羽是谁呢？这里只能简单交代一下：刘大羽是重庆市公安局刑侦队的一员干
将，刚调到荆南市公安局刑侦队来担任副队长之职，其它情况，笔者会在适当的时候详
细介绍。案情就是命令。现在必须派人赶到二龙山的案发现场。
欧阳队长向冯局长汇报过案情以后，冯局长当即决定：欧阳队长立即带人前往二龙
山，接刘大羽同志的工作交由他来完成。
和欧阳平一同前往的有陈杰、左向东、严建华、李化和韩玲玲。李化，大家比较熟
悉吧！他在侦破小鬼巷177号凶杀案的过程所表现出来的聪明才智给我们留下了深刻的
印象。去年春天，欧阳队长把他调到了市公安局刑侦队——昔日的战友又走到一起来了。
天气异常... 阅读全帖 |
|
s******n
发帖数: 3946 | 47 第三题，最后所有的1会扩展成矩形样子吧，丁字形的1会被补上缺口变成矩形。从这个角度分析，是不是有比较好的办法？算法如下：
搜索纵或横相连的1，将其扩展为矩形（相连1的minx, miny, maxx, maxy)。然后如果两个矩形距离只间隔一列/行，则很可能合并两个矩形。重复上述步骤直到没法再扩展。 |
|
