Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <algorithm>
- #include <string.h>
- #include <stdlib.h>
- #include <math.h>
- using namespace std;
- inline int sq(int x) {
- return x*x;
- }
- int dInter(int al, int ar, int bl, int br) {
- if (al>bl) swap(al, bl), swap(ar, br);
- if (al<=bl && ar>=bl) return 0;
- return bl-ar;
- }
- struct seg {
- int l,r,b,t;
- int dist2(seg& a) {
- int d=0;
- d=sq(dInter(this->l, this->r,
- a.l, a.r));
- d+=sq(dInter(this->b, this->t,
- a.b, a.t));
- return d;
- }
- void read() {
- int x,y,len;
- scanf("%d %d %d", &x,&y,&len);
- this->l=this->r=x;
- this->b=this->t=y;
- if (len<0) this->t-=len;
- else this->r+=len;
- }
- };
- const int inf =0x3f3f3f3f;
- int n;
- int g[1010][1010];
- seg s[1010];
- int b,e;
- bool mark[1010];
- void dfs(int v, int maxEdge) {
- mark[v]=true;
- for (int i=0; i<n; i++)
- if (g[v][i]<=maxEdge && !mark[i])
- dfs(i,maxEdge);
- }
- int main() {
- while (1) {
- scanf("%d", &n);
- if (!n) break;
- for (int i=0; i<n; i++)
- s[i].read();
- memset(g,0x3f,sizeof(g));
- for (int i=0; i<n; i++)
- g[i][i]=0;
- for (int i=0; i<n; i++)
- for (int j=i+1; j<n; j++)
- g[i][j]=g[j][i]=s[i].dist2(s[j]);
- for (b=0, e=inf-10; b<e; ) {
- int mid=(b+e)/2;
- memset(mark,0,sizeof(mark));
- dfs(0,mid);
- if (mark[1]) e=mid;
- else b=mid+1;
- }
- printf("%.2lf\n", sqrt(b));
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment