Help in debugging BOI 2012 Mobiles

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

this is the pdf link, see p2 (mobiles).

SOLUTION : binsrch on answer and check. however my code is giving error (WA). its quite small, so hopefully it will be readable.

Any help is appreciated.

PS: main function only has the binary search part. Check function checks if the dist chosen will cover the entire line. i have removed the redundant segments using deque using the fact that the points are already sorted by x coordinate

code

#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <complex>
#include <stack>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>

const ld INF = 1e9+10;
using namespace std;
const int MAXN = 1000*1000+10;

vector<pld> allP;

bool check(ld dist,ld l){
	deque<pld> dq;
	for(auto e : allP){
		ld dd = dist*dist - e.ss*e.ss;
		if(dd < 0)continue;
		dd = sqrt(dd);
		pld r = {e.ff-dd,e.ff+dd};
		while(dq.size() > 0 and dq.back().ff >= r.ff)
			dq.pop_back();
		dq.pb(r);
	}
	if(dq.empty())return 0;
	if(dq.front().ff > 0)return 0;
	ld right = dq[0].ss;
	FORE(i,1,(int)dq.size()-1){
		if(dq[i].ff > dq[i-1].ss)return 0;
		right = max(right,dq[i].ss);
	}
	return right >= l;
}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n,l;
	cin >> n >> l;
	FOR(i,n){
		int a,b;
		cin >> a >> b;
		allP.pb({a,abs(b)});
	}
	ld lo = 0;
	ld hi = 3e9;
	ld best = 1e12;
	while(lo <= hi){
		if(hi-lo < 1e-5){
			break;
		}
		ld mid = (lo+hi)/2;
		if(check(mid,l)){
			best = min(best,mid);
			hi = mid;
		}else{
			lo = mid;
		}
	}
	printf("%.5f\n",(double)best);
	return 0;
}

Comments (5)

Write comment?

RestingRajarshi

6 years ago, # |

Auto comment: topic has been updated by RestingRajarshi (previous revision, new revision, compare).

→ Reply

Tutis

I think that part "I have removed the redundant segments using deque using the fact that the points are already sorted by x coordinate" is incorrect.

6 years ago, # ^ |

let s[i] = starting of range and e[i] = ending of range. if j > i and s[j] < s[i] then obviously e[j] > e[i] right? so the ith interval is completely overlapped by the jth interval.

Thats why i removed.

RestingRajarshi's blog