QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#384397 | #2173. What's Our Vector, Victor? | distant_yesterday | RE | 159ms | 9996kb | C++20 | 5.7kb | 2024-04-09 22:48:28 | 2024-04-09 22:48:28 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef LOCAL
#include "cp_debug.h"
#else
#define debug(...) 42
#endif
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
template<typename T> void read(T &x){
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
read(first);
read(args...);
}
template<typename T> void write(T x) {
if(x > 9) write(x/10);
putchar(x%10 + '0');
}
const double eps = 1e-11;
int sgn(double x) {
if(fabs(x) < eps) return 0;
return x > 0 ? 1 : -1;
}
struct Vec : public vector<double> {
Vec(size_t siz, double val): vector(siz, val) { }
#define v (*this)
double operator * (const Vec& rhs) const {
assert(sz(v) == sz(rhs));
double res = 0;
for(int i = 0; i < sz(v); ++i)
res += v[i] * rhs[i];
return res;
}
Vec operator + (const Vec& rhs) const {
assert(sz(v) == sz(rhs));
Vec res(sz(v), 0);
for(int i = 0; i < sz(v); ++i) res[i] = v[i] + rhs[i];
return res;
}
Vec operator - (const Vec& rhs) const {
assert(sz(v) == sz(rhs));
Vec res(sz(v), 0);
for(int i = 0; i < sz(v); ++i) res[i] = v[i] - rhs[i];
return res;
}
Vec operator += (const Vec& rhs) {
assert(sz(v) == sz(rhs));
for(int i = 0; i < sz(v); ++i) v[i] += rhs[i]; return v;
}
Vec operator -= (const Vec& rhs) {
assert(sz(v) == sz(rhs));
for(int i = 0; i < sz(v); ++i) v[i] -= rhs[i]; return v;
}
Vec operator * (double k) const {
Vec res(v); for(auto &g : res) g *= k;
return res;
}
Vec operator /= (double k) {
for(auto &g: v) g /= k;
return v;
}
#undef v
};
double dis(const Vec& A, const Vec& B) { return (A - B) * (A - B); }
// input: m x (d+1) matrix, meaning [A, b] in Ax=b.
// \sum_{j=0}^{d-1} a[i][j] * x[j] = a[i][d].
// returns:
tuple<bool, Vec, vector<Vec>> gram_schmidt(vector<Vec> a) {
int m = sz(a), d = sz(a[0])-1;
int pos = 0, rc = 0;
vector<int> fre(d), leftp;
rep(i, 0, d) {
int op = -1;
for(int j = pos; j < m; j++) {
if(sgn(a[j][i]) && (op == -1 || fabs(a[j][i]) > fabs(a[op][i]))) {
op = j;
}
}
if(op == -1) { fre[i] = ++rc; continue; }
fre[i] = 0;
if(op != pos) { swap(a[pos], a[op]); }
for(int j = pos+1; j < m; j++) {
double f = a[j][i] / a[pos][i];
a[j] -= a[pos] * f;
}
a[pos] /= a[pos][i];
leftp.push_back(i);
pos++;
}
while(sz(a) > 0) {
const auto &last = a.back();
bool last_zero = fabs(last[d]) < eps;
bool pre_zero = true;
rep(i,0,d) pre_zero = pre_zero && fabs(last[i]) < eps;
if(pre_zero) {
if(!last_zero) return {false, Vec(0,0), {}}; // no solution.
a.pop_back();
} else {
break;
}
}
Vec sol(d, 0.0); // special solution
for(int i = sz(a)-1; i >= 0; --i) {
assert(sgn(a[i][leftp[i]] - 1.0) == 0);
sol[leftp[i]] = a[i][d];
rep(j,0,i) {
double f = a[j][leftp[i]];
a[j] -= a[i] * f;
}
}
vector<Vec> res; // orthonormal null space of A.
for(int f = 1; f <= rc; ++f) {
Vec c(d, 0);
for(int i = 0; i < d; ++i) if(fre[i] == f) c[i] = 1;
for(int i = sz(a)-1; i >= 0; --i) {
for(int j = leftp[i] + 1; j < d; ++j) {
c[leftp[i]] -= c[j] * a[i][j];
}
}
for(auto g : res) c -= g * (c * g);
c /= sqrt(c * c);
res.push_back(c);
}
return {true, sol, res};
}
void solve() {
int d, n;
read(d, n);
vector<Vec> a(n, Vec(d, 0.0));
Vec e(n, 0), norm2(n, 0);
rep(i,0,n) {
rep(j,0,d) {
scanf("%lf", &a[i][j]);
norm2[i] += a[i][j] * a[i][j];
}
scanf("%lf", &e[i]);
}
// mat[i][d] -- rhs
vector<Vec> mat(n-1, Vec(d+1, 0.0));
rep(i,0,n-1) {
rep(j,0,d) {
mat[i][j] = (a[i][j]-a[n-1][j]);
}
mat[i][d] = 0.5 * ((norm2[i]-norm2[n-1]) - e[i]*e[i] + e[n-1]*e[n-1]);
}
if(n == 1) {
rep(i,0,d) {
printf("%.11f%c", a[0][i]+(i==0?e[0]:0)," \n"[i==d-1]);
}
return;
}
// the plane -- sol + C*res for any C in R^{dim(null(A))}
auto [success, sol, res] = gram_schmidt(mat);
assert(success);
if(sz(res) == 0) {
rep(i,0,d) {
printf("%.11f%c", sol[i]," \n"[i==d-1]);
}
return;
}
// the ball -- centered at a[n-1] with e[n-1]
auto min_vec = sol - a[n-1];
for(auto g: res) {
min_vec -= g * (min_vec * g);
}
double min_vec_length_sqr = min_vec*min_vec;
assert(min_vec_length_sqr <= e[n-1]*e[n-1]);
double walk_dist = sqrt(e[n-1]*e[n-1]-min_vec_length_sqr);
auto final_point = a[n-1]+min_vec;
if(walk_dist >= 5e-6) {
assert(sz(res) > 0);
final_point += res[0]*walk_dist;
}
rep(i,0,d) {
printf("%.11f%c", final_point[i]," \n"[i==d-1]);
}
}
signed main() {
int T; T = 1;
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 155ms
memory: 9796kb
input:
500 500 60.00268893933372283 70.35885554610950976 -8.98574176457012186 46.16014112676185732 66.31422279348288384 29.03050764912902082 -35.06996828144599476 -59.10319321730690234 67.85808505028276727 20.30232033048615392 62.38784996896146140 59.92659390534240060 -36.26787439344059294 30.8251981981496...
output:
19.21314202324 6.61160103842 21.42004827104 56.93864780695 -89.71604746871 92.93228900637 70.95769159999 11.49554277966 -48.36859404983 38.69381072098 50.07742920705 7.62861162427 2.21480565127 -37.31399084293 -95.50612141061 -67.78347667255 -6.43422579940 45.24694340818 -27.51574560987 19.963864243...
result:
ok accepted
Test #2:
score: 0
Accepted
time: 159ms
memory: 9912kb
input:
500 500 -20.46791708061053328 -78.90373004342441732 -47.09421721341704625 49.96697218958462372 48.99528416466444014 -46.87780686216100889 73.68284736943891744 -53.69249802982882613 -92.37158007019175443 -97.95346943385396798 -47.79109018973426259 82.31965483504592385 -72.09718577745493917 -32.376534...
output:
-1.52153450791 4.56939357265 -55.15374000490 -30.82061230787 -4.53007111746 -40.74804909282 -98.08174663875 -70.67943356687 33.75800057876 40.83078719875 -79.97010236612 28.76110614563 74.11693817693 99.20066097362 63.14666159688 13.48723862520 87.81528089994 -79.24851687056 -94.83717688756 -18.8682...
result:
ok accepted
Test #3:
score: 0
Accepted
time: 158ms
memory: 9848kb
input:
500 500 91.75754360584323877 -74.07465057030329092 -30.06919963013949371 -22.45376960826932589 -94.33818252302211249 95.43185666705545600 -35.93139380204742395 -46.28091101025437837 20.25588702053946122 -31.98355965847254367 96.27926708531694544 17.21195108047088240 -16.00480323252260462 -14.1553994...
output:
26.96797408424 -85.51968875917 33.00515250809 56.44917679004 96.20241920521 2.14496497969 46.15930107783 -10.55247728842 95.18780892288 89.03670346652 53.30991399636 47.81093648086 -44.11493615188 -38.68117788514 20.30004648906 -79.55956738281 -83.21872812692 81.04064196283 63.60969293991 -32.594959...
result:
ok accepted
Test #4:
score: 0
Accepted
time: 158ms
memory: 9996kb
input:
500 500 53.59239375857157484 1.29576452891167548 -55.60357761919549802 2.89491049833583247 -72.25117082444128869 -44.92736039007480997 6.81675337705620166 -46.20517542139523925 20.56179110027964896 99.93596620202598046 -30.87710828002636276 60.42621397022924157 79.91458345844398536 94.56182305252031...
output:
25.33192619121 6.05132002659 41.15146068661 -77.21568857928 76.99183184581 80.56904900522 93.06870053691 -33.38783398486 -33.19327080732 -89.27631785301 60.99356088547 21.82363145809 -91.88044701368 76.37558475542 26.48459291942 -41.67736557504 16.22086461861 81.94662678579 29.06951444011 -11.928903...
result:
ok accepted
Test #5:
score: 0
Accepted
time: 155ms
memory: 9840kb
input:
500 500 -63.61543927507285190 43.87221058298641196 8.16924114047013461 -34.92232278546450175 91.80142804719758942 -76.82013016900501157 25.06001121373941487 48.24958448628115093 65.82846176112221315 33.19899446519090702 84.05389321600614494 -78.49637158041961982 87.99406312213668002 -60.859516869891...
output:
8.13485701729 -23.75727998672 -99.86678436736 78.59682054002 4.68676492974 -52.35495792473 -60.65258081641 45.10868303403 75.54516051786 -86.72220987406 46.02924842327 -47.95422161433 -96.31557085191 1.05814364859 63.37179287013 96.96924624431 99.73104802134 87.26535881989 4.43819857234 4.1533345617...
result:
ok accepted
Test #6:
score: -100
Runtime Error
input:
24 114 19.60728784212125220 62.05571106800468328 -77.66722345143722350 83.32150488873739391 85.61849285200199233 -61.26186974500755866 54.01645372221616981 -19.69713224000579999 -10.16958551834513003 -18.69109461054532062 9.59051520125903778 91.21514401069063638 89.60632230190051928 -51.201061482129...