「BZOJ4014」[FJOI2014] 病毒防护带
根据点到直线距离公式
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)计算答案
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<map> #include<ctime> #include<vector> #include<set> #include<cmath> #include<algorithm> #define inf 1000000000 #define ll long long #define ld long double #define eps 1e-6 #define pi acos(-1) using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n; int a,b,c; ll x[1000005],y[1000005]; ll sx,sy,sx2,sy2,sxy; ld cal(ld K,ld b) { return (K*K*sx2+sy2+b*b*n-2*K*sxy-2*b*sy+2*b*K*sx)/(K*K+1); } ld solve(ld K) { ld l=-1e9,r=1e9; for(int i=1;i<=100;i++) { ld x1=(r-l)/3+l,x2=(r-l)/3*2+l; ld t1=cal(K,x1),t2=cal(K,x2); if(t1>t2)l=x1; else r=x2; } return cal(K,l); } int main() { // freopen("vir.in","r",stdin); // freopen("vir.out","w",stdout); T=read(); for(int cas=1;cas<=T;cas++) { sx=sy=sx2=sy2=sxy=0; printf("Case %d: ",cas); n=read(); x[1]=read();y[1]=read(); a=read();b=read();c=read(); for(int i=2;i<=n;i++) { x[i]=(a*x[i-1]*x[i-1]+b*x[i-1]+c)%107; y[i]=(a*y[i-1]*y[i-1]+b*y[i-1]+c)%107; } for(int i=1;i<=n;i++) { sx+=x[i];sy+=y[i]; sx2+=x[i]*x[i];sy2+=y[i]*y[i]; sxy+=x[i]*y[i]; } ld l=-1e9,r=1e9; for(int i=1;i<=100;i++) { ld x1=(r-l)/3+l,x2=(r-l)/3*2+l; ld t1=solve(x1),t2=solve(x2); if(t1>t2)l=x1; else r=x2; } printf("%.5lf\n",(double)solve(l)*pi/n); } return 0; } |
Subscribe
计数器 9858043
OI 课件=>
OI 课件=>