力扣149. 直线上最多的点数

〇〇

〇〇 发表于 2024-9-9 01:29
把斜率法做出来了with recursive t as (select [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4],[0,5]] p),t1 as(sel ...

长度法，精度要改为1e10才够
D copy (from t) to 'd:/149-data.csv';
Run Time (s): real 0.003 user 0.000000 sys 0.000000

with recursive t1(rn,zb) as(select rn::int rn, zb::int[] zb from 'd:/149-data.csv')
   ,b as(select t1.rn d1,t2.rn d2,sqrt(pow((t1.zb[1]-t2.zb[1]),2)+pow((t1.zb[2]-t2.zb[2]),2)) ju from t1,t1 t2 where t1.rn<>t2.rn)
   ,a(lv,dd1,dd2,ps,ju0)as(select 1,d1,d2,[d1,d2],ju from b
   union all
   select lv+1,dd1,dd2,list_append(ps,t1.rn),ju0 from a ,t1,b b1,b b2 where (not list_has(ps,t1.rn)) and
   b1.d1=dd1 and b1.d2=t1.rn
   and b2.d1=dd2 and b2.d2=t1.rn
   and (abs(ju0+b1.ju-b2.ju)<1e-10 or abs(b2.ju+b1.ju-ju0)<1e-10 or abs(ju0+b2.ju-b1.ju)<1e-10)
   )
select max(length(ps)) from a;
┌─────────────────┐
│ max(length(ps)) │
│      int64      │
├─────────────────┤
│               3 │
└─────────────────┘
Run Time (s): real 17.808 user 39.764655 sys 1.918812

newkid

〇〇 发表于 2024-9-9 12:17
create table t as select row_number()over(order by 1)rn,zb from(select distinct [(random()*100000):: ...

斜率会不会有误差问题？比如两条线经过四舍五入变成斜率相同

〇〇

与长度相比，它的误差已经比较小了