(UVA) 1216 - The Bug Sensor Problem

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=3657

其實這題跟 UVA 10369 一樣 XD

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <queue>
using namespace std;

typedef pair<double,double> pdd;
const int MAX_N = 1e5+6;
const double INF = 1e9+7;

inline double dis(pdd a,pdd b) {
 return sqrt((a.first-b.first)*(a.first-b.first) + (a.second-b.second)*(a.second-b.second));
}

double d[MAX_N];
pdd v[MAX_N];
bool visit[MAX_N];
int parent[MAX_N];  //to collect edge, we need that!

double Prim(int n,int m) {
priority_queue<double> que;

double mx=0.0;

 for (int x=0;n>x;x++) {
  d[x] = 1e9+7;
  visit[x]=false;
 }

 d[0]=0.0;
 parent[0]=0;

 for (int x=0;n>x;x++) {
  double min=INF;
  int p;
  for (int y=0;n>y;y++) {
   if (visit[y]==false && d[y]<min) {
    p=y;
    min=d[y];
   }
  }
  //we select p
  visit[p]=true;
  que.push(dis(v[p],v[parent[p]]));
//  cout<<"get "<<p<<" & "<<parent[p]<<endl;
  for (int y=0;n>y;y++) {
   if (visit[y]==false && dis(v[p],v[y]) < d[y]) {
    d[y] = dis(v[p],v[y]);
    parent[y]=p;
   }
  }
 }
 for (int x=0;m-1>x;x++) que.pop();
 return que.top();
}

int main () {
// freopen("output.txt","w",stdout);
 int T;
 scanf("%d",&T);
 for (int qq=0;T>qq;qq++) {
  int m,n=0;
  scanf("%d",&m);
  int x=0;
  while(1) {
 
   int i,j;
   scanf("%d",&i);
   if (i!=-1) scanf("%d",&j);
   else break;
   v[x]=make_pair(i,j);
   n++;
   x++;
  }
  double ret=Prim(n,m);
  if (ret - int(ret) > 1e-9) printf("%d\n",int(ret) + 1);
  else printf("%.0f\n",ret);
 }
// puts("");
}