「BZOJ4014」[FJOI2014] 病毒防护带

2014年12月3日3,7440

根据点到直线距离公式
ans=min(Σ(kxi-yi+b)^2 / (k^2 + 1))
这个可以三分套三分算。。。我不会偏导不会证
展开->

(k^2x^2-2*k*x*y+y^2+2*b*k*x-2*b*y+b^2)/(k^2+1)

预处理出Σxi、Σxi、Σyi、Σxi^2、Σyi^2、Σxiyi
可以O(1)计算答案

 

 

avatar
  Subscribe  
提醒