#include #include #include #include using namespace std; #define MAXVAR 50 #define MAXCONSTRAINT 25*49 #define lptype double #define EPS 1e-7 //Simplex input // Maximizes CX subject to AX <= B with X >= 0 lptype C[MAXVAR]; lptype A[MAXCONSTRAINT][MAXVAR]; lptype B[MAXCONSTRAINT]; //simplex temporaries lptype tableau[MAXCONSTRAINT + 1][MAXVAR + MAXCONSTRAINT + 2]; //Returns CX lptype simplex(int variables, int constraints) { //Initialize tablueau int rows = constraints; //Note rows and cols doesn't count the outermost row/col for convenience int cols = variables + constraints + 1; for(int i = 0; i < constraints; i++) { for(int j = 0; j < variables; j++) tableau[i][j] = A[i][j]; for(int j = 0; j < constraints; j++) tableau[i][j + variables] = i == j ? 1 : 0; tableau[i][variables + constraints] = 0; tableau[i][variables + constraints + 1] = B[i]; } for(int j = 0; j < variables; j++) tableau[constraints][j] = C[j] == 0 ? 0 : -C[j]; for(int j = 0; j < constraints; j++) tableau[constraints][j + variables] = 0; tableau[constraints][variables + constraints] = 1; tableau[constraints][variables + constraints + 1] = 0; //Pivot until done while(true) { //Select pivot column int pivot_col = 0; for(int i = 1; i < cols; i++) if(tableau[rows][i] < tableau[rows][pivot_col]) pivot_col = i; //Check for finishing condition if(tableau[rows][pivot_col] >= 0) break; //Select pivot row int pivot_row = 0; for(int i = 1; i < rows; i++) if(tableau[i][pivot_col] >= EPS) if(tableau[pivot_row][pivot_col] < EPS || tableau[i][cols] / tableau[i][pivot_col] < tableau[pivot_row][cols] / tableau[pivot_row][pivot_col]) pivot_row = i; //Perform pivot for(int i = 0; i <= rows; i++) { if(i == pivot_row) continue; lptype ratio = tableau[i][pivot_col] / tableau[pivot_row][pivot_col]; for(int j = 0; j <= cols; j++) tableau[i][j] -= ratio * tableau[pivot_row][j]; tableau[i][pivot_col] = 0; //should already be zero, just to keep things precise } //Normalize table for(int i = 0; i <= rows; i++) { double mx = 0; for(int j = 0; j <= cols; j++) { mx = max(mx, fabs(tableau[i][j])); } for(int j = 0; j <= cols; j++) { tableau[i][j] /= mx; } } } return tableau[rows][cols] / tableau[rows][cols - 1]; } double XC[MAXVAR]; double YC[MAXVAR]; int main() { for(int t = 1; ; t++) { memset(A, 0, sizeof(A)); memset(B, 0, sizeof(B)); memset(C, 0, sizeof(C)); int N; cin >> N; if(!N) break; int p = 0; for(int i = 0; i < N; i++) { C[i] = 1; cin >> XC[i] >> YC[i]; for(int j = 0; j < i; j++) { A[p][i] = 1; A[p][j] = 1; B[p++] = sqrt((XC[i] - XC[j]) * (XC[i] - XC[j]) + (YC[i] - YC[j]) * (YC[i] - YC[j])); } } printf("%.2f\n", simplex(N, p)); } return 0; }