SHARE
TWEET

Will Indiana Jones Get There? AC - Live Archive 2613

royalsflush Sep 10th, 2012 30 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <string.h>
  4. #include <stdlib.h>
  5. #include <math.h>
  6. using namespace std;
  7.  
  8. inline int sq(int x) {
  9.         return x*x;
  10. }
  11.  
  12. int dInter(int al, int ar, int bl, int br) {
  13.         if (al>bl) swap(al, bl), swap(ar, br);
  14.  
  15.         if (al<=bl && ar>=bl) return 0;
  16.         return bl-ar;
  17. }
  18.  
  19. struct seg {
  20.         int l,r,b,t;
  21.  
  22.         int dist2(seg& a) {
  23.                 int d=0;
  24.  
  25.                 d=sq(dInter(this->l, this->r,
  26.                         a.l, a.r));
  27.                 d+=sq(dInter(this->b, this->t,
  28.                         a.b, a.t));
  29.                 return d;
  30.         }
  31.  
  32.         void read() {
  33.                 int x,y,len;
  34.                 scanf("%d %d %d", &x,&y,&len);
  35.                 this->l=this->r=x;
  36.                 this->b=this->t=y;
  37.                
  38.                 if (len<0) this->t-=len;
  39.                 else this->r+=len;
  40.         }
  41. };
  42.  
  43. const int inf =0x3f3f3f3f;
  44.  
  45. int n;
  46. int g[1010][1010];
  47. seg s[1010];
  48. int b,e;
  49. bool mark[1010];
  50.  
  51. void dfs(int v, int maxEdge) {
  52.         mark[v]=true;
  53.  
  54.         for (int i=0; i<n; i++)
  55.                 if (g[v][i]<=maxEdge && !mark[i])
  56.                         dfs(i,maxEdge);
  57. }
  58.  
  59. int main() {
  60.         while (1) {
  61.                 scanf("%d", &n);
  62.                 if (!n) break;
  63.  
  64.                 for (int i=0; i<n; i++)
  65.                         s[i].read();
  66.        
  67.                 memset(g,0x3f,sizeof(g));
  68.  
  69.                 for (int i=0; i<n; i++)
  70.                         g[i][i]=0;
  71.  
  72.                 for (int i=0; i<n; i++)
  73.                         for (int j=i+1; j<n; j++)
  74.                                 g[i][j]=g[j][i]=s[i].dist2(s[j]);
  75.  
  76.                 for (b=0, e=inf-10; b<e; ) {
  77.                         int mid=(b+e)/2;
  78.                         memset(mark,0,sizeof(mark));
  79.                         dfs(0,mid);
  80.  
  81.                         if (mark[1]) e=mid;
  82.                         else b=mid+1;
  83.                 }
  84.  
  85.                 printf("%.2lf\n", sqrt(b));
  86.         }
  87.         return 0;
  88. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top