[Codeforces] 832C. Strange Radiation

題目連結:http://codeforces.com/problemset/problem/832/C

---

煩躁的一題...還因為沒注意到一定要放在整數點卡了一段時間QQ。
作法大概就是對答案二分搜，而驗證的時候，則會發現若是考慮要讓某個人往右的人達到終點，如果直接放在他身上可以，那往他左邊一點可能也可以，所以可以求出一個區間 ；同理往左的也是。這樣就轉化成為先將一堆區間填在數線上，接著詢問一堆區間是否與先前的區間們有碰在一起的地方。而找出對於往右區間的方法這裡是列了$$\frac{x-x^\prime}{s-v}+\frac{10^6-\frac{x-x^\prime}{s-v}\cdot v-x}{s+v} \leq t\\x^\prime \geq 10^6-\frac{v(10^6-x-vt)}{s}-st$$往左的則是$$\frac{x^\prime-x}{s-v}+\frac{x-\frac{x^\prime-x}{s-v}\cdot v}{s+v} \leq t\\x^\prime \leq \frac{v(x-vt)}{s}+st$$

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second
typedef long double llf;
typedef long long lld;
const int N = 1e6 + 5;

int n, s;
vector<PII> L, R;
lld arr[N];

inline bool isOK(llf);

int main(){
	cin>>n>>s;
	for(int i=0;i<n;i++){
		PII tp; cin>>tp.FF>>tp.SS;
		int x; cin>>x;
		if(x-1) R.PB(tp);
		else L.PB(tp);
	}
	llf l = 0, r = 1e6;
	for(int _=0;_<80;_++){
		llf mid = (l+r)/2;
		if(isOK(mid)) r=mid;
		else l=mid;
	}
	cout<<fixed<<setprecision(20)<<r<<'\n';
	return 0;
}

inline bool isOK(llf t){
	#define x FF
	#define v SS
	auto Add = [](int l, int r){
		arr[l]++;
		arr[r+1]--;
	};
	auto Sum = [](int l, int r){
		if(!l) return arr[r];
		else return arr[r]-arr[l-1];
	};
	const int RR = 1e6;
	fill(arr, arr+N, 0);
	for(auto i: R){
		if(RR-i.v*(RR-i.x-i.v*t)/(llf)s-s*t > i.x) continue;
		if((llf)(RR-i.x)/i.v <= t){
			Add(0, RR);
		}else{
			Add(max(ceil(RR-i.v*(RR-i.x-i.v*t)/s-s*t), (llf)0), i.x);
		}
	}
	for(int i=1;i<N;i++) arr[i]+=arr[i-1];
	for(int i=1;i<N;i++) arr[i]+=arr[i-1];
	for(auto i: L){
		if(s*t+i.v*(i.x-i.v*t)/(llf)s < i.x) continue;
		if((llf)i.x/i.v <= t){
			return Sum(0, RR);
		}
		if(Sum(i.x, min(floor(s*t+i.v*(i.x-i.v*t)/(llf)s), (llf)RR)) > 0){
			return true;
		}
	}
	return false;
	#undef x
	#undef v
}