New start Day 2 (1/10/2020) codeforces 492B Vanya and Lantern

 question: (source: https://codeforces.com/problemset/problem/492/B)

    Vanya And Lantern

Vanya walks late at night along a straight street of length l, lit by n lanterns. Consider the coordinate system with the beginning of the street corresponding to point 0, and its end corresponding to the point l. Then the i-th lantern is at the point ai. The lantern lights all points of the street that are at the distance of at most d from it, where d is some positive number, common for all lanterns.

Vanya wonders: what is the minimum light radius d should the lanterns have to light the whole street?

Input

The first line contains two integers n, l (1 ≤ n ≤ 1000, 1 ≤ l ≤ 109) — the number of lanterns and the length of the street respectively.

The next line contains n integers ai (0 ≤ ai ≤ l). Multiple lanterns can be located at the same point. The lanterns may be located at the ends of the street.

Output

Print the minimum light radius d, needed to light the whole street. The answer will be considered correct if its absolute or relative error doesn't exceed 10 - 9.

Examples

input

Copy

7 15
15 5 3 7 9 14 0

output

Copy

2.5000000000

input

Copy

2 5
2 5

output

Copy

2.0000000000

Note

Consider the second sample. At d = 2 the first lantern will light the segment [0, 4] of the street, and the second lantern will light segment [3, 5]. Thus, the whole street will be lit.

My logic:

It's a good question and cannot be done using any brute force method. The array has to be sorted first. Since the number of lamps is not more than 1000, we can sort the array using any sorted algorithm but it's not a good solution. We need to sort our array in the shortest time using quick sort or merge sort. I  used merge sort which took a bit of time to implement because of my silliest error.

 After sorting we need to find the max distance between consecutive two lamps. let it be called "maxdis".

the light between this has to be covered by two lamps so each lamp will take half of the area, so the answer will be maxdis/2 but we need to consider the ends too. We need to check the distance between the first lamp from the origin and the last lamp from the end of the lane. These areas need to be covered by single lamps so we don't divide them by 2.

My code:

	#include<bits/stdc++.h>
	#define ll long long int
	#define li long int
	#define pb push_back
	#define mp make_pair
	using namespace std;
	void mergee(ll arr[],ll l,ll m,ll r)
	{
	ll i,j,k;
	ll n1=m-l+1;
	ll n2=r-m;
	ll L[n1];
	ll R[n2];
	for(i=0;i<n1;i++)
	{
	L[i]=arr[l+i];
	}
	for(j=0;j<n2;j++)
	{
	R[j]=arr[m+j+1];
	}
	i=0;
	j=0;
	k=l;
	while(i<n1&&j<n2)
	{
	if(L[i]<=R[j])
	{
	arr[k]=L[i];
	i++;
	}
	else
	{
	arr[k]=R[j];
	j++;
	}
	k++;
	}
	while(i<n1)
	{
	arr[k]=L[i];
	i++;
	k++;
	}
	while(j<n2)
	{
	arr[k]=R[j];
	j++;
	k++;
	}
	}
	void mergesort(ll l,ll r,ll arr[])
	{
	if(l<r)
	{
	ll m=l+((r-l)/2);
	mergesort(l,m,arr);
	mergesort(m+1,r,arr);
	mergee(arr,l,m,r);
	}
	}
	int main()
	{
	ll mod=1000000007;
	ll t,n,i,j,k,l,sum=0,flag=0,m,q,temp;
	cin>>n>>l;
	ll arr[n];
	for(i=0;i<n;i++)
	{
	cin>>arr[i];
	}
	mergesort(0,n-1,arr);
	ll maxdis=-1;
	for(i=1;i<n;i++)
	{
	if(arr[i]-arr[i-1]>maxdis)
	{
	maxdis=arr[i]-arr[i-1];
	}
	}
	if(2*(arr[0]-0)>maxdis)
	{
	maxdis=2*(arr[0]-0);
	}
	if(2*(l-arr[n-1])>maxdis)
	{
	maxdis=2*(l-arr[n-1]);
	}
	double answer=(double)maxdis/(double)2;
	printf("%.9f",answer);
	return 0;
	}

view raw Vanya and lantern 492b hosted with ❤ by GitHub