转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
题目:行星围绕着恒星转,飞船用最少的时间抵达行星上,不能距离恒星太近,问最少时间。
二分答案,然后可以算出行星的末位置,计算出飞船到目标位置的最短距离,判断一下最短距离是否小于飞船的速度乘以时间。
其中最短距离分为两种情况,可以是直线,可能是两条切线+一段弧。
其中那段弧的圆心角是先计算出两点之间的夹角,然后减去两个直角三角形的内角。
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<vector>
#define eps 1e-10
#define LL long long
#define LD long double
#define pi acos(-1.0)
using namespace std;
struct Point{
LD x,y;
}per,qwe,goal,central;
LD v,vp,r,R,ang;
LD Dist(Point p1,Point p2){
return (LD)sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
LD slove(LD t){
LD angle=(ang+t*vp/R); //目标位置的角度
goal.x=R*cos(angle),goal.y=R*sin(angle); //目标位置坐标
//cout<<goal.x<<" "<<goal.y<<endl;
LD qiexian1=sqrt(qwe.x*qwe.x+qwe.y*qwe.y-r*r); //起始位置与恒星安全区的切线长度
LD qiexian2=sqrt(goal.x*goal.x+goal.y*goal.y-r*r); //目标位置与恒星安全区的切线长度
LD dist=Dist(qwe,goal); //起始位置与目标位置之间的距离
if(dist<qiexian2+qiexian1) { //从起始位置到目标位置的直线与安全区不相交
// cout<<dist<<endl;
return dist;
}
else{
LD dist1=Dist(qwe,central);
LD dist2=Dist(goal,central);
LD centralangle=acos((dist1*dist1+dist2*dist2-dist*dist)/(2*dist1*dist2))-atan(qiexian1/r)-atan(qiexian2/r); //扇形的圆心角
// cout<<centralangle*r+qiexian1+qiexian2<<endl;
return centralangle*r+qiexian1+qiexian2;
}
}
int main(){
central.x=central.y=0;
while(scanf("%lf%lf%lf%lf%lf%lf%lf",&per.x,&per.y,&vp,&qwe.x,&qwe.y,&v,&r)!=EOF){
ang=atan2(per.y,per.x); //行星初始角度
R=sqrt(per.x*per.x+per.y*per.y); //行星轨迹半径
LD high=1000000,low=0,mid;
while(high-low>eps){
mid=(low+high)/2;
if(slove(mid)<=eps+mid*v)
high=mid;
else
low=mid;
}
printf("%.10f\n",mid);
}
return 0;
}
/*
10 0 1
-10 0 2 8
50 60 10
50 60 20 40
*/
分享到:
相关推荐
Codeforces Round #723 (Div. 2).md
开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include #include #include #include #include #include #...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
上面代码跑出来的dp[n][m]是0,然后从(1,1)(1,2)(2,2)(2,3)这样的相与值是k (看懂ans+k是啥应该就懂了) 代码: int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans=(1&...
传送门 题意: 一个长度为n的数组,为删除一些数后,剩下的数能否构成长度大于3的回文数组 思路: 只要能找到两个相等的数,且他们的间距大于2即可 o(n^2)的暴力就能过 比赛时写了一个o(n)的 就是把所有相等的数放到...
第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一个bbb的位置对字符串进行分组,然后找到第kkk个字符串在第几组里即可,然后再推出第二个bbb的位置...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
C. Ehab and Path-etic MEXs 题意 给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。...
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about palindromes. He learned that a...
直接输出1,n-1即可 #include #include #include #include #include #include #include #include #include #include #define pb push_back #define lb lower_bound #define ub upper_bound #define rep(i,a,b) for...
这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #define lowbit(x) (x &(-x)) using namespace std; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); ...
A #include using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll x; cin>>x; cout<<1>>t; while(t--){ st.clear(); ll n; cin >>n; ll re
题解:6nlogn,先sort三个数组a,b,c, 六次枚举二分查找,再每次min找最小值,例如:先固定数组a,再在数组b,c中利用lower_bound找到第一个大于等于a[i]的数, #pragma GCC optimize(2) #include #define ll long long...
将所有数字看成2进制,从最高位看起,如果第i位上为1的数只有一个的话,那么这个数必然对答案有贡献,就把它排在第一个,后面任意排。 例:11,6,4,0 二进制表示为:1011,110,100,0 右起第四位为1的只有1011,...
惭愧,前几天刚学的dfs序判祖先关系都忘了用。。 这题我们先把所有点都变成父亲节点(根节点不变),这样只需要判所有节点是否在一条链上。 由于判断x是y的祖先:需要满足:st[x]<=st[y]<...
B. Yet Another Palindrome Problem 题目链接-B. Yet Another Palindrome Problem 题目大意 给一个长为n(≤5000)的数组,问是否存在一个长度至少为3的子序列是回文的,子序列的数可以不连续但是相对顺序不可变 ...
F. Moving Points time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output There are n points on a coordinate axis OX. The i-th point is located at the ...