QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#377446#8102. MallSolitaryDream#WA 1ms3796kbC++172.0kb2024-04-05 13:44:042024-04-05 13:44:06

Judging History

你现在查看的是最新测评结果

  • [2024-04-05 13:44:06]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3796kb
  • [2024-04-05 13:44:04]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
typedef long long ll;
typedef double db;
const int N=1e5+50;
pair<int,int> a[N];
db X2[N],Y2[N],X[N],Y[N],XY[N];
db x[N],y[N];
void solve(db A,db F,db B,db C,db D,db E,db &k,db &b,db &s) {
    db e=2*A/C;
    b=(E*e-D)/(C-2*F*e);
    k=(-D-C*b)/2*A;
    s=A*k*k+F*b*b+B+C*k*b+D*k+E*b;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    FOR(i,1,n) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a+1,a+n+1);
    FOR(i,1,n) {
        x[i]=a[i].first;
        y[i]=a[i].second;
        X2[i]=X2[i-1]+(db)a[i].first*a[i].first;
        X[i]=X[i-1]+(db)a[i].first;
        Y2[i]=Y2[i-1]+(db)a[i].second*a[i].second;
        Y[i]=Y[i-1]+(db)a[i].second;
        XY[i]=XY[i-1]+(db)a[i].first*a[i].second;
    }
    if(n<=2) {
        cout << "0\n";
        return 0;
    }
    db ans=1e100;
    FOR(i,2,n-2) {
        db k1,b1,s1,k2,b2,s2;
        solve(X2[i],i,Y2[i],2*X[i],-2*XY[i],-2*Y[i],k1,b1,s1);
        solve(X2[n]-X2[i],n-i,Y2[n]-Y2[i],2*(X[n]-X[i]),-2*(XY[n]-XY[i]),-2*(Y[n]-Y[i]),k2,b2,s2);
        if(fabs(k1-k2)>1e-9) {
            db p=(b2-b1)/(k1-k2);
            if(p>=a[i].first && p<=a[i+1].first) {
                ans=min(ans,s1+s2);
            }
        }
    }
    FOR(i,2,n-1) {
        db A1=X2[i-1]-2*x[i]*X[i-1]+x[i]*x[i]*(i-1),F1=i-1,B1=Y2[i-1],C1=2*(X[i-1]-x[i]*(i-1)),D1=-2*(XY[i-1]-x[i]*Y[i-1]),E1=-2*Y[i-1];
        db A2=(X2[n]-X2[i])-2*x[i]*(X[n]-X[i])+x[i]*x[i]*(n-i),F2=n-i,B2=(Y2[n]-Y2[i]),C2=2*(X[n]-X[i]-x[i]*(n-i))
            ,D2=-2*(XY[n]-XY[i]-x[i]*(Y[n]-Y[i])),E2=-2*(Y[n]-Y[i]);
        db A=1,B=-2*y[i],C=y[i]*y[i];
        A+=F1,B+=E1,C+=B1,A-=C1*C1/4/A1,B-=2*C1*D1/4/A1,C-=D1*D1/4/A1;
        A+=F2,B+=E2,C+=B2,A-=C2*C2/4/A2,B-=2*C2*D2/4/A2,C-=D2*D2/4/A2;
        ans=min(ans,(4*A*C-B*B)/4/A);
    }
    cout << ans << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3796kb

input:

4 4
1 2
2 2 4
2 1 3
1 1

output:

1e+100

result:

wrong answer Oczekiwano "YES", wczytano ""