puzzleup 2020 11月开始

〇〇

到原网址看到图了，不斜的 1*1 36 个，2*2 25 个，斜的面积为2 5 9 25...

newkid

jihuyao 发表于 2020-12-10 10:48
Let me throw a brick.  Each square can be identified by its rid, cid, and length.  If all are ordere ...

看了你的定义，你似乎认为正方形的边不是横的就是竖的？斜放的的也很多。

jihuyao

Ha, I certainly missed that point.  So add one more direction in 45 degree with different length for any square group starting at the same point (top left corner).  This part to list all valid squares should be straight.  But the next part may become complicated to check if there exists any shared point for any given two squares in the generated square list in the first part.  For any pair of normal and normal it is easy to tell.  For any pair of normal and abnormal it is still able to picture by moving up/down and left/right.  Can someone produce the gem for any pair of abnormal and abnormal.  Hopefully there still exists a formula based on the position and length.

newkid

jihuyao 发表于 2020-12-11 12:16
Ha, I certainly missed that point.  So add one more direction in 45 degree with different length for ...

斜的可不止45度，你仔细看一下，我的图已经补充到56楼了。

solomon_007

newkid 发表于 2020-12-10 02:25
第一步，先构造出所有正方形，我弄出105个，有没人来对一下答案。剩下的工作是找一个算法判断一个点是否在 ...

先实现第一步：

105 个有效正方形

----------------
with t as (select level n from dual connect by level <= 6),
     p as (select row_number() over(order by t1.n,t2.n) rn,t1.n x,t2.n y from t t1,t t2)
select p1.x x1,p1.y y1,
       p2.x x2,p2.y y2,
       p3.x x3,p3.y y3,
       p4.x x4,p4.y y4
  from p p1,p p2,p p3,p p4
where p1.rn < p2.rn
   and p2.rn < p3.rn
   and p3.rn < p4.rn
   and ( (p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y) = 0  
      or (p2.x-p1.x)*(p3.x-p2.x)+(p2.y-p1.y)*(p3.y-p2.y) = 0 )
   and ( (p2.x-p1.x)*(p4.x-p2.x)+(p2.y-p1.y)*(p4.y-p2.y) = 0 and (p3.x-p1.x)*(p4.x-p3.x)+(p3.y-p1.y)*(p4.y-p3.y) = 0
      or (p4.x-p3.x)*(p3.x-p2.x)+(p4.y-p3.y)*(p3.y-p2.y) = 0 and (p4.x-p1.x)*(p2.x-p1.x)+(p4.y-p1.y)*(p2.y-p1.y) = 0
       )
   and ( power((p2.x-p1.x),2)+power((p2.y-p1.y),2) = power((p4.x-p1.x),2)+power((p4.y-p1.y),2)
      or power((p2.x-p1.x),2)+power((p2.y-p1.y),2) = power((p3.x-p1.x),2)+power((p3.y-p1.y),2)
       );
   
--思路，正方形4个顶点，p1p2p3p4, 先取p1, 再取p2,  这样 p1p2 就产生了一个边的向量，
--取第3个点p3, 那么 p1p2 垂直于边向量 p1p3 或 p2p3
--当区第四个顶点 p4,那么 p4p1 垂直于边向量 p1p2 ,或者 p3p1 垂直于边向量 p1p2
--再根据 向量垂直，则两个向量的内积或点积=0 即 <p1p2,p1p3>=0 就是 (p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y) = 0
--最后相邻边长相等

solomon_007

newkid 发表于 2020-12-10 02:25
第一步，先构造出所有正方形，我弄出105个，有没人来对一下答案。剩下的工作是找一个算法判断一个点是否在 ...

第一步 105 是对的：

with t as (select level n from dual connect by level <= 6),
     p as (select row_number() over(order by t1.n,t2.n) rn,t1.n x,t2.n y from t t1,t t2)
select p1.x x1,p1.y y1,
       p2.x x2,p2.y y2,
       p3.x x3,p3.y y3,
       p4.x x4,p4.y y4
  from p p1,p p2,p p3,p p4
where p1.rn < p2.rn
   and p2.rn < p3.rn
   and p3.rn < p4.rn
   and ( (p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y) = 0  
      or (p2.x-p1.x)*(p3.x-p2.x)+(p2.y-p1.y)*(p3.y-p2.y) = 0 )
   and ( (p2.x-p1.x)*(p4.x-p2.x)+(p2.y-p1.y)*(p4.y-p2.y) = 0 and (p3.x-p1.x)*(p4.x-p3.x)+(p3.y-p1.y)*(p4.y-p3.y) = 0
      or (p4.x-p3.x)*(p3.x-p2.x)+(p4.y-p3.y)*(p3.y-p2.y) = 0 and (p4.x-p1.x)*(p2.x-p1.x)+(p4.y-p1.y)*(p2.y-p1.y) = 0
       )
   and ( power((p2.x-p1.x),2)+power((p2.y-p1.y),2) = power((p4.x-p1.x),2)+power((p4.y-p1.y),2)
      or power((p2.x-p1.x),2)+power((p2.y-p1.y),2) = power((p3.x-p1.x),2)+power((p3.y-p1.y),2)
       );

solomon_007

105 ， p1p2p3p4 固定画一个图就可以，不用考虑位置的或关系

with t as (select level n from dual connect by level <= 6),
     p as (select row_number() over(order by t1.n,t2.n) rn,t1.n x,t2.n y from t t1,t t2)
select p1.x x1,p1.y y1,
       p2.x x2,p2.y y2,
       p3.x x3,p3.y y3,
       p4.x x4,p4.y y4
  from p p1,p p2,p p3,p p4
where p1.rn < p2.rn
   and p2.rn < p3.rn
   and p3.rn < p4.rn
   and (p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y) = 0  
   and (p2.x-p1.x)*(p4.x-p2.x)+(p2.y-p1.y)*(p4.y-p2.y) = 0 and (p3.x-p1.x)*(p4.x-p3.x)+(p3.y-p1.y)*(p4.y-p3.y) = 0
   and power((p2.x-p1.x),2)+power((p2.y-p1.y),2) = power((p3.x-p1.x),2)+power((p3.y-p1.y),2)
       ;

solomon_007

# 6

SQL>  with t as (select level n from dual connect by level <= 6),
  2        p as (select row_number() over(order by t1.n,t2.n) rn,t1.n x,t2.n y from t t1,t t2),
  3        s as (
  4  select p1.x x1,p1.y y1,
  5         p2.x x2,p2.y y2,
  6         p3.x x3,p3.y y3,
  7         p4.x x4,p4.y y4
  8    from p p1,p p2,p p3,p p4
  9   where p1.rn < p2.rn
10     and p2.rn < p3.rn
11     and p3.rn < p4.rn
12     and (p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y) = 0
13     and (p2.x-p1.x)*(p4.x-p2.x)+(p2.y-p1.y)*(p4.y-p2.y) = 0 and (p3.x-p1.x)*(p4.x-p3.x)+(p3.y-p1.y)*(p4.y-p3.y) = 0
14     and power((p2.x-p1.x),2)+power((p2.y-p1.y),2) = power((p3.x-p1.x),2)+power((p3.y-p1.y),2)
15  )
16  select
17         /*s1.x1 x1,s1.y1 y1,
18         s1.x2 x2,s1.y2 y2,
19         s1.x3 x3,s1.y3 y3,
20         s1.x4 x4,s1.y4 y4,
21         s2.x1 x5,s2.y1 y5,
22         s2.x2 x6,s2.y2 y6,
23         s2.x3 x7,s2.y3 y7,
24         s2.x4 x8,s2.y4 y8 */
25         count(*)
26    from s s1,s s2
27   where (  (s2.x1-s1.x1)*(s1.x3-s1.x1)+(s2.y1-s1.y1)*(s1.y3-s1.y1) < 0
28        or  (s2.x1-s1.x1)*(s1.x2-s1.x1)+(s2.y1-s1.y1)*(s1.y2-s1.y1) < 0
29        or  (s2.x1-s1.x2)*(s1.x2-s1.x1)+(s2.y1-s1.y2)*(s1.y2-s1.y1) < 0
30        or  (s2.x1-s1.x2)*(s1.x3-s1.x1)+(s2.y1-s1.y2)*(s1.y3-s1.y1) < 0 )
31    and (   (s2.x2-s1.x1)*(s1.x3-s1.x1)+(s2.y2-s1.y1)*(s1.y3-s1.y1) < 0
32        or  (s2.x2-s1.x1)*(s1.x2-s1.x1)+(s2.y2-s1.y1)*(s1.y2-s1.y1) < 0
33        or  (s2.x2-s1.x2)*(s1.x2-s1.x1)+(s2.y2-s1.y2)*(s1.y2-s1.y1) < 0
34        or  (s2.x2-s1.x2)*(s1.x3-s1.x1)+(s2.y2-s1.y2)*(s1.y3-s1.y1) < 0 )
35    and (   (s2.x3-s1.x1)*(s1.x3-s1.x1)+(s2.y3-s1.y1)*(s1.y3-s1.y1) < 0
36        or  (s2.x3-s1.x1)*(s1.x2-s1.x1)+(s2.y3-s1.y1)*(s1.y2-s1.y1) < 0
37        or  (s2.x3-s1.x2)*(s1.x2-s1.x1)+(s2.y3-s1.y2)*(s1.y2-s1.y1) < 0
38        or  (s2.x3-s1.x2)*(s1.x3-s1.x1)+(s2.y3-s1.y2)*(s1.y3-s1.y1) < 0 )
39    and (   (s2.x4-s1.x1)*(s1.x3-s1.x1)+(s2.y4-s1.y1)*(s1.y3-s1.y1) < 0
40        or  (s2.x4-s1.x1)*(s1.x2-s1.x1)+(s2.y4-s1.y1)*(s1.y2-s1.y1) < 0
41        or  (s2.x4-s1.x2)*(s1.x2-s1.x1)+(s2.y4-s1.y2)*(s1.y2-s1.y1) < 0
42        or  (s2.x4-s1.x2)*(s1.x3-s1.x1)+(s2.y4-s1.y2)*(s1.y3-s1.y1) < 0 )
43  /

  COUNT(*)
----------
      4451

solomon_007

65 楼，判断一个点是否在矩形外，方法是： 由P点到矩形的 p1p2p3p4 连线，这4个向量与矩形边的向量（判断垂直的两个就够了）的内积或点积 小于0 ，
有一个小于0就判断点 P 在其外。因为由P点到矩形的 p1p2p3p4 连线，这4个向量中至少有一个与矩形边的向量的夹角会大于 90度，cos值小于0

solomon_007

p-p3,p-p4的条件好像没有列，修改一下：

SQL>
SQL>  with t as (select level n from dual connect by level <= 6),
  2        p as (select row_number() over(order by t1.n,t2.n) rn,t1.n x,t2.n y from t t1,t t2),
  3        s as (
  4  select p1.x x1,p1.y y1,
  5         p2.x x2,p2.y y2,
  6         p3.x x3,p3.y y3,
  7         p4.x x4,p4.y y4
  8    from p p1,p p2,p p3,p p4
  9   where p1.rn < p2.rn
10     and p2.rn < p3.rn
11     and p3.rn < p4.rn
12     and (p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y) = 0
13     and (p2.x-p1.x)*(p4.x-p2.x)+(p2.y-p1.y)*(p4.y-p2.y) = 0 and (p3.x-p1.x)*(p4.x-p3.x)+(p3.y-p1.y)*(p4.y-p3.y) = 0
14     and power((p2.x-p1.x),2)+power((p2.y-p1.y),2) = power((p3.x-p1.x),2)+power((p3.y-p1.y),2)
15  )
16  select
17         /*s1.x1 x1,s1.y1 y1,
18         s1.x2 x2,s1.y2 y2,
19         s1.x3 x3,s1.y3 y3,
20         s1.x4 x4,s1.y4 y4,
21         s2.x1 x5,s2.y1 y5,
22         s2.x2 x6,s2.y2 y6,
23         s2.x3 x7,s2.y3 y7,
24         s2.x4 x8,s2.y4 y8 */
25         count(*)
26    from s s1,s s2
27   where ( (s2.x1-s1.x1)*(s1.x3-s1.x1)+(s2.y1-s1.y1)*(s1.y3-s1.y1) < 0
28        or (s2.x1-s1.x1)*(s1.x2-s1.x1)+(s2.y1-s1.y1)*(s1.y2-s1.y1) < 0
29        or (s2.x1-s1.x2)*(s1.x3-s1.x1)+(s2.y1-s1.y2)*(s1.y3-s1.y1) < 0
30        or (s2.x1-s1.x2)*(s1.x2-s1.x1)+(s2.y1-s1.y2)*(s1.y2-s1.y1) < 0
31        or (s2.x1-s1.x3)*(s1.x3-s1.x1)+(s2.y1-s1.y3)*(s1.y3-s1.y1) < 0
32        or (s2.x1-s1.x3)*(s1.x2-s1.x1)+(s2.y1-s1.y3)*(s1.y2-s1.y1) < 0
33        or (s2.x1-s1.x4)*(s1.x3-s1.x1)+(s2.y1-s1.y4)*(s1.y3-s1.y1) < 0
34        or (s2.x1-s1.x4)*(s1.x2-s1.x1)+(s2.y1-s1.y4)*(s1.y2-s1.y1) < 0 )
35    and  ( (s2.x2-s1.x1)*(s1.x3-s1.x1)+(s2.y2-s1.y1)*(s1.y3-s1.y1) < 0
36        or (s2.x2-s1.x1)*(s1.x2-s1.x1)+(s2.y2-s1.y1)*(s1.y2-s1.y1) < 0
37        or (s2.x2-s1.x2)*(s1.x3-s1.x1)+(s2.y2-s1.y2)*(s1.y3-s1.y1) < 0
38        or (s2.x2-s1.x2)*(s1.x2-s1.x1)+(s2.y2-s1.y2)*(s1.y2-s1.y1) < 0
39        or (s2.x2-s1.x3)*(s1.x3-s1.x1)+(s2.y2-s1.y3)*(s1.y3-s1.y1) < 0
40        or (s2.x2-s1.x3)*(s1.x2-s1.x1)+(s2.y2-s1.y3)*(s1.y2-s1.y1) < 0
41        or (s2.x2-s1.x4)*(s1.x3-s1.x1)+(s2.y2-s1.y4)*(s1.y3-s1.y1) < 0
42        or (s2.x2-s1.x4)*(s1.x2-s1.x1)+(s2.y2-s1.y4)*(s1.y2-s1.y1) < 0 )
43    and  ( (s2.x3-s1.x1)*(s1.x3-s1.x1)+(s2.y3-s1.y1)*(s1.y3-s1.y1) < 0
44        or (s2.x3-s1.x1)*(s1.x2-s1.x1)+(s2.y3-s1.y1)*(s1.y2-s1.y1) < 0
45        or (s2.x3-s1.x2)*(s1.x3-s1.x1)+(s2.y3-s1.y2)*(s1.y3-s1.y1) < 0
46        or (s2.x3-s1.x2)*(s1.x2-s1.x1)+(s2.y3-s1.y2)*(s1.y2-s1.y1) < 0
47        or (s2.x3-s1.x3)*(s1.x3-s1.x1)+(s2.y3-s1.y3)*(s1.y3-s1.y1) < 0
48        or (s2.x3-s1.x3)*(s1.x2-s1.x1)+(s2.y3-s1.y3)*(s1.y2-s1.y1) < 0
49        or (s2.x3-s1.x4)*(s1.x3-s1.x1)+(s2.y3-s1.y4)*(s1.y3-s1.y1) < 0
50        or (s2.x3-s1.x4)*(s1.x2-s1.x1)+(s2.y3-s1.y4)*(s1.y2-s1.y1) < 0 )
51    and  ( (s2.x4-s1.x1)*(s1.x3-s1.x1)+(s2.y4-s1.y1)*(s1.y3-s1.y1) < 0
52        or (s2.x4-s1.x1)*(s1.x2-s1.x1)+(s2.y4-s1.y1)*(s1.y2-s1.y1) < 0
53        or (s2.x4-s1.x2)*(s1.x3-s1.x1)+(s2.y4-s1.y2)*(s1.y3-s1.y1) < 0
54        or (s2.x4-s1.x2)*(s1.x2-s1.x1)+(s2.y4-s1.y2)*(s1.y2-s1.y1) < 0
55        or (s2.x4-s1.x3)*(s1.x3-s1.x1)+(s2.y4-s1.y3)*(s1.y3-s1.y1) < 0
56        or (s2.x4-s1.x3)*(s1.x2-s1.x1)+(s2.y4-s1.y3)*(s1.y2-s1.y1) < 0
57        or (s2.x4-s1.x4)*(s1.x3-s1.x1)+(s2.y4-s1.y4)*(s1.y3-s1.y1) < 0
58        or (s2.x4-s1.x4)*(s1.x2-s1.x1)+(s2.y4-s1.y4)*(s1.y2-s1.y1) < 0 )
59  /

  COUNT(*)
----------
      6906