2023湖南省赛

宝石交易

floyd然后固定a,枚举b开始位置
1s2e8 -_-

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define ft first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f

#define int long long
const int N = 10010;
int n, m;
int a[N], b[2*N];
int f[410][410];
void solve(){
        cin >> n >> m;
        for(int i = 1; i <= n; i ++) cin >> a[i];
        for(int i = 1; i <= n; i ++) cin >> b[i];
        for(int i = 1; i <= n; i ++) b[i + n] = b[i];

        

        for(int i = 1; i <= 400; i ++)
        for(int j = 1; j <= 400; j ++) f[i][j] = (i == j)?0:inf;
        while(m --){
            int x, y, z;
            cin >> x >> y >> z;
            f[x][y] = min(f[x][y], z);
            f[y][x] = f[x][y];
        }
        for(int k = 1; k <= 400; k ++){
            for(int i = 1; i <= 400; i ++){
                for(int j = 1; j <= 400; j ++){
                    if(f[i][k] > inf/2 || f[k][j] > inf/2) continue;
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
                }
            }
        }
        // for(int  i = 1; i <= 5; i ++){
        //     for(int  j = 1; j <= 5; j ++) cout << f[i][j] << " \n"[j == 5];
        // }

        ll ans = INF;
        for(int st = 1; st <= n; st ++){
            ll tmp = 0;
            int i = 1; int j = st;
            while(i <= n ){
   if(f[a[i]][b[j]] > inf/2){
                    tmp = INF;
                    break;
                }
                tmp += 1ll*f[a[i]][b[j]];
                i ++; j ++;
            }
            ans = min(ans, tmp);
        }
        reverse(a + 1, a + n + 1);
        reverse(b + 1, b + 2*n + 1);
          for(int st = 1; st <= n; st ++){
            ll tmp = 0;
            int i = 1; int j = st;
            while(i <= n ){
                if(f[a[i]][b[j]] > inf/2){
                    tmp = INF;
                    break;
                }
                tmp += 1ll*f[a[i]][b[j ]];
                i ++ ;
                j ++;
            }
            ans = min(ans,  tmp);
        }
        if(ans > INF/2) cout << -1 << '\n';
        else 
        cout << ans << '\n';
}

signed main(){
    std::ios::sync_with_stdio(false);
    int T = 1; 
    // cin >> T;
    while(T--){
        solve();
    }
}

radius

枚举球心在三个坐标轴上，二分半径
ck 每个点能被包含 所需要的球心位置区间，差分离散化后前缀和>=n/2

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ft first
#define se second
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef __int128 LL;
typedef long double ld;
typedef pair<long double, int> pli;
typedef pair<int, int> pii;

int n;
const ld eps = 1e-10;
ld y[4][100005];

vector<pli> vec;

int sgn(ld x, ld y){
    if(fabs(x - y) < eps) return 0;
    if(x > y) return 1;
    else  return -1;
}

bool ck(int o, ld r){
    vec.clear();
    for(int i = 1; i <= n; i ++){
        ld c = 0;
        for(int j = 0; j < 3; j ++){
            if(j != o)
            c += y[j][i] * y[j][i];
        }
        if(sgn(r * r, c) < 0) continue;
        c = sqrt(r * r - c);
        // ld c = s[i] - ;

        ld y1 = y[o][i] - c;
        ld y2 = y[o][i] + c;
        vec.pb({y1, 1});
        vec.pb({y2, -1});
    }


    sort(vec.begin(), vec.end());
    int nn = -1;
    for(int i = 0; i < vec.size(); i ++){
        if(nn == -1 || vec[i].ft != vec[nn].ft){
            vec[++ nn] = vec[i];
        }
        else vec[nn].se += vec[i].se;
    }
    for(int i = 0; i <= nn; i ++){
        if(i != 0) vec[i].se += vec[i - 1].se;
        if(vec[i].se >= (n / 2)) return 1;
    }
    return 0;
}

ld work(int o){
    ld l = 0; ld r = 20000;
    while(r - l > eps){
        ld mid = (l + r) / 2;
        if(ck(o, mid)) r = mid;
        else l = mid;
    }
    return l;
}

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> y[0][i] >> y[1][i] >> y[2][i];
    }
    ld ans = work(0);
    ans = min(ans, work(1));
    ans = min(ans, work(2));
    cout << fixed << setprecision(7) << ans << '\n';
}

signed main()
{
    std::ios::sync_with_stdio(false);
    
    int T = 1;
    // cin >> T;
    while(T -- ){
        solve();
    }
}