数据结构与算法老师吴冬令营讨论.pdfVIP

题目一.照明

有N个光源，位置给定，但是可以旋转。每个都照射夹角为2pi/N的无限远

区域，如下图所示：

请你把每个光源旋转到合适的角度，使得N个光源合在一起照亮了整个平

面，例如：

y

x

输入：n个光源各自的位置

输出：n个光源各自照射的角度（用照射范围线的极角表示）

样例输入

3

00

20

11

样例输出：（对应上图）

0.52359877559829887

2.61799387799149437

4.71238898038468986

讨论：

1.是否一定存在解？（答案：一定存在）

2.如果存在，如何求出一组解？（略）

题目二：铺砖问题

设想我们用1*2的小砖铺满5*6的地面，至少有以下两种方法：

方案(a)是有缝的，因为我们可以沿着左数第4列切一刀把地面分成两部分

而不会损坏任何一块砖

方案(b)是无缝的，不管是水平的缝还是竖直的缝都没有。

把问题一般化，用p*q砖来铺a*b的地面，是否可以得到无缝铺法？

输入：

第一行是一个整数n，表示有n组数据待你判断。

第二行到第n+1行，每一行一组数据，分别是p,q,a,b(1=p,q,a,b=10000)四个整

数，每两个数之间用一个空格隔开。

输出：

输出n行字符串，每行为Yes或No