Submission #10467423

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define nl '\n'
#define deb(x) cerr<<#x" = "<<x<<nl
#define in() ( { int a ; scanf("%d", &a); a; } )
//#define double long double
const int N = 70;
const int mod = 1e9 + 7;
const double eps = 1e-9;

inline ll sqr(int x){return x*x;}

struct PT
{
    int x,y;
    PT() {}
};
ll dist(PT a,PT b)
{
    return sqr(a.x-b.x)+sqr(a.y-b.y);
}
//5 - outside and do not intersect
//4 - intersect outside in one point
//3 - intersect in 2 points
//2 - intersect inside in one point
//1 - inside and do not intersect
int circle_circle_relation(PT a, int ci, PT b, int cj, double x)
{
    ll d=dist(a,b) * ci * ci * cj * cj;
    double q = x * (ci + cj);
    q *= q;
    if(fabs(d * 1.0 - q) < eps) return 1;
    if(d * 1.0 > q) return 5;
    return 1;
}
///cliques are subsets of vertices, all adjacent to each other, also called complete subgraphs
///maximum clique is a clique with the largest possible number of vertices

///Complexity (3^(n/3)) , where n is the number of nodes
int g[70][70];
///for each i every nodes j!=i must need to be set 1 if
///there is any edge between i and j
///1-indexed
int res;
long long edges[70];
void BronKerbosch(int n, long long R, long long P, long long X) {
    if (P == 0LL && X == 0LL) {
        int t = 0;
        for (int i = 0; i < n; i++) if ((1ll << i) & R) t ++;
        res = max(res, t);
        return;
    }
    long long u = 0;
    while (!((1ll<<u) & (P|X))) u ++;
    for (int v = 0; v < n; v++) {
        if (((1ll << v) & P) && !((1ll << v) & edges[u])) {
            BronKerbosch(n, R | (1ll << v), P & edges[v], X & edges[v]);
            P -= (1ll << v);
            X |= (1ll << v);
        }
    }
}

int max_clique (int n) {
    res = 0;
    for(int i = 0; i <= n; i++) edges[i] = 0;
    for (int i = 1; i <= n; i++) {
        edges[i] = 0;
        for (int j = 1; j <= n; j++)  if (g[i][j]) edges[i - 1] |= ( 1ll << (j - 1) );
    }
    BronKerbosch(n, 0, (1ll << n) - 1, 0);
    return res;
}
int c[N];
PT p[N];
int yo(double x, int n)
{
    for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) g[i][j] = 0;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){
        if(circle_circle_relation(p[i], c[i], p[j], c[j], x) != 5) g[i][j] = 1;
    }
    for(int i =1 ; i <= n; i++) g[i][i] = 0;
    return max_clique(n);
}
int32_t main()
{
    int n, k; cin >> n >> k;
    if(k == 1){
            cout << fixed << setprecision(10) << 0.0 << nl;
    }
    for(int i = 1; i <= n; i++){
        int a, b, x;  cin >> a >> b >> x; p[i]. x= a, p[i]. y = b; c[i] = x;
    }
    auto it = 5000;
    double l = 0.0, r = 1.0e9;
    while(it--){
        double mid = (l + r) * 0.5;
        if(yo(mid, n) >= k) r = mid;
        else l = mid;
    }
    cout << fixed << setprecision(10) << l << nl;
    return 0;
}

Submission Info

Judge Result