QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#377446 | #8102. Mall | SolitaryDream# | WA | 1ms | 3796kb | C++17 | 2.0kb | 2024-04-05 13:44:04 | 2024-04-05 13:44:06 |
Judging History
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 ""