CrazedBoar

NC223524. CrazedBoar

描述

A crazed boar has become lost in the forest! In its madness, it will charge in a random direction at blazing speed, until it has traveled a distance d, or until it hits a tree (in which case the boar will become dazed and end its charge), whichever comes first. Given the layout of trees around the boar, what is the probability the boar completes its wild charge without hitting a tree? We will model the forest as the $xy_{}$ plane, with the boar a disk of radius b that begins centered at the origin (0, 0). We will also represent the trees as disks, with varying radii $r_i$ and centers $(x_i,y_i)$ . The boar charges by choosing a direction uniformly at random, and then translating in that direction for a distance d. The boar hits a tree and becomes dazed if, at any point during its charge, the boar’s body has nonzero area of overlap with any tree.

输入描述

The first line of input contains a single integer n (0 ≤ n ≤ 10 000), the number of trees in the forest. n lines follow,each of which contain three integers , and , denoting the position and radius of the  tree. These inputs satisfy  ≤ ≤  and 0 < ≤  . The final line of input contains two integer b and d, the radius of the boar(0 < b ≤  ) and the distance that the boar will charge (0 ≤ d ≤ 106). You may assume that no tree overlaps withor touches the boar at the start of its charge (but trees might overlap or touch each other).

输出描述

Print a single real number: the probability that the boar completes its charge without hitting any tree. Your answer willbe considered correct if it has absolute or relative error at most   .

示例1

输入:

1
3 0 1
1 4

输出:

0.76772047

示例2

输入:

输出:

0.19253205

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 24ms, 内存消耗: 1376K, 提交时间: 2021-08-19 14:11:52

#include<bits/stdc++.h>
using namespace std;
#define double long double
const int N=20010;
const double pi=3.141592653589793;
int n;
double x[N],y[N],r[N];

pair<double,int> e[N*4];int c=0;
int main(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>x[i]>>y[i]>>r[i];
	double tmp,D;
	cin>>tmp>>D;
	for(int i=0;i<n;i++)r[i]+=tmp;
	
	for(int i=0;i<n;i++){
		double x=::x[i],y=::y[i],r=::r[i];
		double a=atan2(y,x);
		double l=sqrt(x*x+y*y);
		if(r+D<l)continue;
		double beg=0,end=0;
		double d=D;
		d=min(d,sqrt(l*l-r*r));
		if(l*l-r*r<0)while(1);
		beg=-(end=acos((d*d+l*l-r*r)/2/d/l));
		beg+=a;end+=a;
		beg=fmod(beg+pi*10,pi*2);
		end=fmod(end+pi*10,pi*2);
		if(beg>end){
			e[c++]={0,1};
			e[c++]={end,-1};
			e[c++]={beg,1};
			e[c++]={pi*2,-1};
		}else{
			e[c++]={beg,1};
			e[c++]={end,-1};
		}
	}
	sort(e,e+c);
	double ans=0;
	for(int i=0,t=0;i<c;i++){
		if(t)ans+=e[i].first-e[i-1].first;
		t+=e[i].second;
	}
	cout<<fixed<<setprecision(8)<<1-ans/pi/2<<endl;
}

上一题

下一题

详情