QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #705193 | #1077. Goat Ropes | TheZone | AC ✓ | 7ms | 4968kb | C++14 | 6.0kb | 2024-11-02 22:29:33 | 2024-11-02 22:29:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#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()
#define PB push_back
#define FS first
#define SD second
typedef pair<int, int> pii;
typedef vector<int> vi;
template<class X, class Y> X cmx(X &a, Y b) { a = max<X>(a, b); }
#define ary(k) array<int, k>
typedef double T;
typedef vector<T> vd;
typedef vector<vd> vvd;
const T eps = 1e-8, inf = 1/.0;
#define MP make_pair
#define ltj(X) if (s==-1 || MP(X[j],N[j]) < MP(X[s], N[s])) s=j
struct LPSolver {
int m, n;
vi N, B;
vvd D;
LPSolver(const vvd& A, const vd& b, const vd& c) :
m(sz(b)), n(sz(c)), N(n+1), B(m), D(m+2, vd(n+2)) {
rep(i,0,m) rep(j,0,n) D[i][j] = A[i][j];
rep(i,0,m) { B[i] = n+i; D[i][n] = -1; D[i][n+1] = b[i];}
rep(j,0,n) { N[j] = j; D[m][j] = -c[j];}
N[n] = -1; D[m+1][n] = 1;
}
void pivot(int r, int s) {
T *a = D[r].data(), inv = 1 / a[s];
rep(i,0,m+2) if (i!=r && abs(D[i][s]) > eps) {
T *b = D[i].data(), inv2 = b[s] * inv;
rep(j,0,n+2) b[j] -= a[j] * inv2;
b[s] = a[s] * inv2;
}
rep(j,0,n+2) if (j != s) D[r][j] *= inv;
rep(i,0,m+2) if (i != r) D[i][s] *= -inv;
D[r][s] = inv;
swap(B[r], N[s]);
}
bool simplex(int phase) {
int x = m + phase - 1;
for(;;) {
int s = -1;
rep(j, 0, n+1) if (N[j] != -phase) ltj(D[x]);
if (D[x][s] >= -eps) return true;
int r = -1;
rep(i,0,m) {
if (D[i][s] <= eps) continue;
if (r == -1 || MP(D[i][n+1] / D[i][s], B[i])
< MP(D[r][n+1] / D[r][s], B[r])) r = i;
}
if (r == -1) return false;
pivot(r, s);
}
}
T solve(vd &x) {
int r = 0;
rep(i,1,m) if (D[i][n+1] < D[r][n+1]) r = i;
if (D[r][n+1] < -eps) {
pivot(r, n);
if (!simplex(2) || D[m+1][n+1] < -eps) return -inf;
rep(i,0,m) if (B[i] == -1) {
int s = 0;
rep(j,1,n+1) ltj(D[i]);
pivot(i, s);
}
}
bool ok = simplex(1); x = vd(n);
rep(i,0,m) if (B[i] < n) x[B[i]] = D[i][n+1];
return ok ? D[m][n+1] : inf;
}
};
int x[1002], y[1002];
signed main() {
cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
while (true) {
int n;
cin >> n;
if (n == 0)
break;
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
}
auto A = vvd(n*(n-1)/2, vd(n, 0));
auto b = vd(n*(n-1)/2);
auto c = vd(n, 1);
auto xx = vd(n, 0);
int it = 0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
A[it][i] = A[it][j] = 1;
b[it] = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
it++;
}
}
LPSolver simplex(A, b, c);
double res = simplex.solve(xx);
cout << fixed << setprecision(2) << res << "\n";
}
}
/*#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#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()
#define PB push_back
#define FS first
#define SD second
typedef pair<int, int> pii;
typedef vector<int> vi;
template<class X, class Y> X cmx(X &a, Y b) { a = max<X>(a, b); }
#define ary(k) array<int, k>
typedef double T;
typedef vector<T> vd;
typedef vector<vd> vvd;
const T eps = 1e-8, inf = 1/.0;
#define MP make_pair
#define ltj(X) if (s==-1 || MP(X[j],N[j]) < MP(X[s], N[s])) s=j
struct LPSolver {
int m, n;
vi N, B;
vvd D;
LPSolver(const vvd& A, const vd& b, const vd& c) :
m(sz(b)), n(sz(c)), N(n+1), B(m), D(m+2, vd(n+2)) {
rep(i,0,m) rep(j,0,n) D[i][j] = A[i][j];
rep(i,0,m) { B[i] = n+i; D[i][n] = -1; D[i][n+1] = b[i];}
rep(j,0,n) { N[j] = j; D[m][j] = -c[j];}
N[n] = -1; D[m+1][n] = 1;
}
void pivot(int r, int s) {
T *a = D[r].data(), inv = 1 / a[s];
rep(i,0,m+2) if (i!=r && abs(D[i][s]) > eps) {
T *b = D[i].data(), inv2 = b[s] * inv;
rep(j,0,n+2) b[j] -= a[j] * inv2;
b[s] = a[s] * inv2;
}
rep(j,0,n+2) if (j != s) D[r][j] *= inv;
rep(i,0,m+2) if (i != r) D[i][s] *= -inv;
D[r][s] = inv;
swap(B[r], N[s]);
}
bool simplex(int phase) {
int x = m + phase - 1;
for(;;) {
int s = -1;
rep(j, 0, n+1) if (N[j] != -phase) ltj(D[x]);
if (D[x][s] >= -eps) return true;
int r = -1;
rep(i,0,m) {
if (D[i][s] <= eps) continue;
if (r == -1 || MP(D[i][n+1] / D[i][s], B[i])
< MP(D[r][n+1] / D[r][s], B[r])) r = i;
}
if (r == -1) return false;
pivot(r, s);
}
}
T solve(vd &x) {
int r = 0;
rep(i,1,m) if (D[i][n+1] < D[r][n+1]) r = i;
if (D[r][n+1] < -eps) {
pivot(r, n);
if (!simplex(2) || D[m+1][n+1] < -eps) return -inf;
rep(i,0,m) if (B[i] == -1) {
int s = 0;
rep(j,1,n+1) ltj(D[i]);
pivot(i, s);
}
}
bool ok = simplex(1); x = vd(n);
rep(i,0,m) if (B[i] < n) x[B[i]] = D[i][n+1];
return ok ? D[m][n+1] : inf;
}
};
int x[1002], y[1002];
signed main() {
cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
while (true) {
int n;
cin >
}*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 4968kb
input:
2 250 250 250 750 3 250 250 500 500 250 750 43 125 365 239 657 166 943 552 850 645 229 66 804 14 657 874 74 892 822 24 316 954 85 654 735 889 469 815 430 547 361 610 709 410 960 519 704 812 160 74 995 852 380 595 540 515 968 825 972 568 255 569 573 497 195 277 205 474 586 596 995 685 439 778 343 792...
output:
500.00 603.55 1963.59 1183.94 1523.39 1400.54 1896.29 1150.63 936.44 2090.95 1911.05 2234.85 1882.07 2220.37 2136.99 2703.45 1952.93 2168.05 2326.30 2077.42 2355.24 2414.20
result:
ok 22 lines