首页 > 代码库 > Miaomiao's Geometry
Miaomiao's Geometry
HDU 4932 Bestcoder
Problem Description
There are N point on X-axis . Miaomiao would like to cover them ALL by using segments with same length.
There are 2 limits:
1.A point is convered if there is a segments T , the point is the left end or the right end of T.
2.The length of the intersection of any two segments equals zero.
For example , point 2 is convered by [2 , 4] and not convered by [1 , 3]. [1 , 2] and [2 , 3] are legal segments , [1 , 2] and [3 , 4] are legal segments , but [1 , 3] and [2 , 4] are not (the length of intersection doesn‘t equals zero), [1 , 3] and [3 , 4] are not(not the same length).
Miaomiao wants to maximum the length of segements , please tell her the maximum length of segments.
For your information , the point can‘t coincidently at the same position.
There are 2 limits:
1.A point is convered if there is a segments T , the point is the left end or the right end of T.
2.The length of the intersection of any two segments equals zero.
For example , point 2 is convered by [2 , 4] and not convered by [1 , 3]. [1 , 2] and [2 , 3] are legal segments , [1 , 2] and [3 , 4] are legal segments , but [1 , 3] and [2 , 4] are not (the length of intersection doesn‘t equals zero), [1 , 3] and [3 , 4] are not(not the same length).
Miaomiao wants to maximum the length of segements , please tell her the maximum length of segments.
For your information , the point can‘t coincidently at the same position.
Input
There are several test cases.
There is a number T ( T <= 50 ) on the first line which shows the number of test cases.
For each test cases , there is a number N ( 3 <= N <= 50 ) on the first line.
On the second line , there are N integers Ai (-1e9 <= Ai <= 1e9) shows the position of each point.
There is a number T ( T <= 50 ) on the first line which shows the number of test cases.
For each test cases , there is a number N ( 3 <= N <= 50 ) on the first line.
On the second line , there are N integers Ai (-1e9 <= Ai <= 1e9) shows the position of each point.
Output
For each test cases , output a real number shows the answser. Please output three digit after the decimal point.
Sample Input
3
3
1 2 3
3
1 2 4
4
1 9 100 10
Sample Output
1.000
2.000
8.000
Hint
For the first sample , a legal answer is [1,2] [2,3] so the length is 1. For the second sample , a legal answer is [-1,1] [2,4] so the answer is 2. For the thired sample , a legal answer is [-7,1] , [1,9] , [10,18] , [100,108] so the answer is 8.1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #include<iostream> 5 #include<math.h> 6 7 using namespace std; 8 9 int main()10 {11 int cas,i,n,right,left;12 double res,a[55],b[120];13 cin>>cas;14 while(cas--)15 {16 cin>>n;17 int j=0;18 for(i=0;i<n;i++)19 {20 cin>>a[i];21 }22 sort(a,a+n);23 for(i=1;i<n;i++)24 {25 b[j++]=a[i]-a[i-1];26 b[j++]=(a[i]-a[i-1]) /2 ;27 }28 sort(b,b+j);29 int flag=0;30 j=j-1;31 res=(double)b[j];32 33 while(1)34 {35 right =0; left=0;36 flag=0;37 for(i=1;i<n;i++)38 {39 if(i==n-1) continue;40 if(a[i]-res<a[i-1] && a[i]+res>a[i+1])41 {42 flag=1;43 break;44 }45 if(a[i]-res>=a[i-1]) 46 {47 if(right==1)48 {49 if(a[i]-a[i-1]==res) {left=1; right=0; }50 else if(a[i]-a[i-1]>=2*res) { left=1; right=0; }51 else if(a[i]+res<=a[i+1]) { left=0; right=1; }52 else flag=1;53 }54 else { left=1; right=0; }55 }56 else if(a[i]+res<=a[i+1]) {57 right=1;58 left=0;59 }60 61 }62 if(flag==1) {63 j--;64 res=b[j];65 }66 else 67 {68 printf("%.3lf\n",res);69 break;70 }71 }72 }73 return 0;74 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。