3388693_ac_4438ms_3580k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>

int n;
int x[655], y[655];
double dx[655][655];

inline double vp(int x1,int y1,int x2,int y2) {
    return double(x1*y2-x2*y1);
}

inline double calc(int i,int j,int k) {
    double sn=fabs(vp(x[j]-x[i],y[j]-y[i],x[k]-x[i],y[k]-y[i])/(dx[i][j]*dx[i][k]));
    return dx[j][k]/sn/2;
}

int main() {
    int i, j, k, t;
    scanf("%d",&t);
    while (t--) {
        scanf("%d",&n);
        for(i=0;i<n;i++) {
            scanf("%d%d",&x[i],&y[i]);
        }
        for(i=0;i<n-1;i++)
            for(j=i+1;j<n;j++)
                dx[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
        double max=-1;
        double rid;
        for(i=0;i<n-2;i++) 
            for(j=i+1;j<n-1;j++)
                for(k=j+1;k<n;k++) 
                    if ((rid=calc(i,j,k))>max) 
                        max=rid;
        printf("%.3lf\n",max);
    }
    return 0;
}