|
|
第一题附加题的SQL,
WITH c AS ( ---- 构造九个点坐标
SELECT ROWNUM AS cid,x,y
FROM (
SELECT x,y
FROM (SELECT LEVEL x FROM DUAL CONNECT BY LEVEL<=3)
,(SELECT LEVEL y FROM DUAL CONNECT BY LEVEL<=3)
ORDER BY x,y
)
)
,lines AS ( ---- 枚举所有三点直线
SELECT 1 lid,'123' str FROM DUAL
UNION ALL SELECT 2,'456' FROM DUAL
UNION ALL SELECT 3,'789' FROM DUAL
UNION ALL SELECT 4,'147' FROM DUAL
UNION ALL SELECT 5,'258' FROM DUAL
UNION ALL SELECT 6,'369' FROM DUAL
UNION ALL SELECT 7,'159' FROM DUAL
UNION ALL SELECT 8,'357' FROM DUAL
)
,all_lines AS ( --- 直线上的三个点的全排列，比如123,132,321,...
SELECT REPLACE(SYS_CONNECT_BY_PATH(c,','),',') str
FROM (
SELECT lid,SUBSTR(str,n,1) c
FROM lines,(SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=3)
)
WHERE LEVEL=3
CONNECT BY NOCYCLE lid=PRIOR lid AND C<>PRIOR C
)
,edges as ( ----- 九个点两两构成的所有的线段，两个方向都包括
SELECT c1.cid||c2.cid as eid
,c1.x,c1.y
,c2.x x2,c2.y y2
FROM c c1,c c2
WHERE c1.cid<>c2.cid
)
,crossing as ( ----- 找出所有的交叉线段对, 参考https://segmentfault.com/a/1190000004457595
SELECT m1.eid eid1,m2.eid eid2
FROM edges m1, edges m2
WHERE INSTR(m1.eid,SUBSTR(m2.eid,1,1))=0
AND INSTR(m1.eid,SUBSTR(m2.eid,2,1))=0
AND ((m1.x-m2.x)*(m1.y-m2.y2)-(m1.x-m2.x2)*(m1.y-m2.y))*((m1.x2-m2.x)*(m1.y2-m2.y2)-(m1.x2-m2.x2)*(m1.y2-m2.y))<=0
AND ((m2.x-m1.x)*(m2.y-m1.y2)-(m2.x-m1.x2)*(m2.y-m1.y))*((m2.x2-m1.x)*(m2.y2-m1.y2)-(m2.x2-m1.x2)*(m2.y2-m1.y))<=0
)
,p (pid,vcnt) as ( ---- 递归构造所有多边形，包括重复的
select cast(cid as varchar2(10)) as pid,1 from c WHERE cid IN (1,2,5) ---- 因为结果要求去除对称重复，只需从这三个点开始
UNION ALL
SELECT p.pid||c.cid,p.vcnt+1
FROM p,c
WHERE INSTR(p.pid,c.cid)=0
AND NOT EXISTS (SELECT NULL FROM all_lines WHERE all_lines.str=SUBSTR(p.pid,-2)||c.cid) --- 排除直线
AND NOT EXISTS (SELECT NULL FROM crossing WHERE INSTR(p.pid||c.cid,crossing.eid1)>0 AND INSTR(p.pid||c.cid,crossing.eid2)>0) ---- 排除交叉
)
,all_p AS ( --- 首尾衔接（加上最后一个端点到第一个端点的线段）后再去除交叉和直线
SELECT *
FROM p
WHERE vcnt>=3
AND NOT EXISTS (SELECT NULL FROM crossing WHERE INSTR(p.pid||p.pid,crossing.eid1)>0 AND INSTR(p.pid||p.pid,crossing.eid2)>0)
AND NOT EXISTS (SELECT NULL FROM all_lines WHERE INSTR(p.pid||p.pid,all_lines.str)>0)
)
,tp1 as ( ----- 九个点的旋转/翻转变形模版
SELECT '123456789' tp1 FROM DUAL
UNION ALL SELECT '741852963' tp1 FROM DUAL
UNION ALL SELECT '987654321' tp1 FROM DUAL
UNION ALL SELECT '369258147' tp1 FROM DUAL
UNION ALL SELECT '321654987' tp1 FROM DUAL
UNION ALL SELECT '789456123' tp1 FROM DUAL
UNION ALL SELECT '147258369' tp1 FROM DUAL
UNION ALL SELECT '963852741' tp1 FROM DUAL
)
,rotate(tp2,vcnt,n,last_cid) AS ( ----- 同一个图形的顺时针旋转模版, 比如125和251,512等等其实是同一个图形
SELECT CAST(CHR(ASCII('A')+c2.cid) AS VARCHAR2(10)),c1.cid,1,c2.cid
FROM c c1,c c2
UNION ALL
SELECT rotate.tp2||CHR(ASCII('A')+c.cid),rotate.vcnt,rotate.n+1,c.cid
FROM rotate,c
WHERE rotate.n<rotate.vcnt
AND (c.cid=rotate.last_cid+1 AND c.cid<=rotate.vcnt OR rotate.last_cid=rotate.vcnt AND c.cid=1)
)
,tp2 AS ( ---- 用REVERSE构造出逆时针变换
SELECT tp2,vcnt,MIN(tp2) OVER(PARTITION BY vcnt) as org
FROM (
SELECT tp2,vcnt FROM rotate WHERE vcnt=n AND vcnt>=3
UNION ALL
SELECT REVERSE(tp2),vcnt FROM rotate WHERE vcnt=n AND vcnt>=3
)
)
,tran1 AS ( ---- 第一次变换：九个点坐标的旋转翻转变换
SELECT all_p.pid
,all_p.vcnt
,TRANSLATE(all_p.pid,'123456789',tp1.tp1) as tran_id1
,rownum rn
FROM all_p,tp1
)
,v1 as ( ----- 变换之后把每个端点拆出来，为平移做准备
SELECT pid,tran_id1,to_number(SUBSTR(tran1.tran_id1,n,1)) cid,vcnt,n,rownum rn
FROM tran1
,(SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=9)
WHERE n<=tran1.vcnt
)
,t1 as ( ---- 平移到最靠近原点(纵横坐标都减去同样的偏移)，平移是为了识别出全等多边形，比如124和125
SELECT pid,tran_id1
,X+1-MIN(X) OVER(PARTITION BY pid,tran_id1) X
,Y+1-MIN(Y) OVER(PARTITION BY pid,tran_id1) Y
,n
,vcnt
FROM v1
,c
WHERE v1.cid=c.cid
)
,move1 AS ( ---------- 把平移后的端点再用LISTAGG拼成图形
SELECT pid,vcnt,LISTAGG(c.cid) WITHIN GROUP(ORDER BY n) new_tran_id1
FROM t1,c
WHERE t1.x=c.x AND t1.y=c.y
GROUP BY pid,vcnt,tran_id1
)
select distinct pid2 from ( ----- 再加上顺逆时针变换后取最小值，去除重复
SELECT move1.pid
,MIN(translate(tp2.tp2,tp2.org,new_tran_id1)) as pid2
FROM move1,tp2
WHERE move1.vcnt=tp2.vcnt
GROUP BY move1.pid
)
ORDER BY LENGTH(pid2),pid2;
PID2
------------------------
124
126
127
129
135
137
138
168
1254
1257
1265
1267
1268
1269
1287
1294
1297
1298
1358
1397
1538
1568
1658
2486
12538
12567
12568
12594
12597
12598
12657
12658
12675
12684
12685
12687
12694
12697
12945
12957
12958
12975
13567
13568
13597
15268
24586
125367
125368
125384
125387
125394
125397
125398
125684
125687
125694
125697
125984
126584
126594
126597
126598
126845
126857
126875
126945
126957
126984
1253684
1253687
1253984
1256984
1265984
74 rows selected. |
|
楼主: 〇〇
IP卡
狗仔卡
发表于 2016-7-29 09:08
显身卡
楼主
