POJ 2728 Desert King

最優比率樹

這題常數是在緊神馬阿0.0

不過據說寫迭代法會很快

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
const double eps = 0.0005;
double taba[1001][1001];
double tabb[1001][1001];
int px[1001], py[1001], pz[1001];
double tabc[1001][1001];
double dis[1001];
bool vis[1001];
double tabs(double x){return max(x, -x);}
int main()
{
 int n;
 for(;;){
  scanf("%d", &n);
  if(n == 0) break;
  for(int lx = 0;lx < n;lx++)
   scanf("%d %d %d", px+lx, py+lx, pz+lx);
  double zmin = 10000000, zmax = 0;
  for(int lx = 0;lx < n;lx++)
   zmin = min(zmin,(double) pz[lx]),
   zmax = max(zmax, (double)pz[lx]);
  double dx, dy;
  for(int lx = 0;lx < n;lx++){
   for(int ly = lx;ly < n;ly++){
    dx = (double)(px[lx]-px[ly]), dy = (double)(py[lx]-py[ly]);
    taba[lx][ly] = tabs((double)(pz[lx]-pz[ly]));
    taba[ly][lx] = taba[lx][ly];
    tabb[lx][ly] = sqrt((double)(dx*dx + dy*dy));
    tabb[ly][lx] = tabb[lx][ly];
   }
  }
  double amin = 0, amax = 100;
  int cc = 0;
  while(amax - amin > eps){
   if(cc++ >= 20) printf("%d\n", 1/0);
   double atest = (amax+amin)/2;
   //printf("%.6f\n", atest);
   for(int lx = 0;lx < n;lx++){
    dis[lx] = taba[lx][0] - atest*tabb[lx][0];
    vis[lx] = false;
   }
   double cost = 0;
   vis[0] = true;
   for(int _ = 0;_ < n-1;_++){
    int min_ind = -1;
    for(int ly = 0;ly < n;ly++){
     if(vis[ly]) continue;
     if((min_ind == -1) or (dis[min_ind] >= dis[ly]))
      min_ind = ly;
    }
    if(min_ind == -1) printf("%d\n", 1/0);
    cost += dis[min_ind];
    for(int lx = 0;lx < n;lx++)
     dis[lx] = min(dis[lx], taba[lx][min_ind] - atest*tabb[lx][min_ind]);
    vis[min_ind] = true;
   }
   if(cost < -eps)
    amax = atest;
   else if(cost > eps)
    amin = atest;
   else{
    amin = atest;
    break;
   }
  }
  printf("%.3f\n", amin);
 }
 return 0;
}