fork download
copy 
  1. #include<map>  
  2. #include<set>  
  3. #include<stack>  
  4. #include<cmath>  
  5. #include<ctime>  
  6. #include<vector>  
  7. #include<string>  
  8. #include<bitset>  
  9. #include<cstdio>  
  10. #include<cstdlib>  
  11. #include<cstring>  
  12. #include<climits>  
  13. #include<complex>  
  14. #include<iostream>  
  15. #include<algorithm>  
  16. using namespace std;
  17. int times;
  18. const double inf=1e12,eps=1e-11,pi=acos(-1.);
  19. double ans;
  20. struct ss
  21. {
  22. 	double nowt,nowd,bt;
  23. 	int id,pa;
  24. 	bool operator <(const ss &temp)const
  25. 	{
  26.         return nowt<temp.nowt-eps;
  27. 	}
  28. };
  29. set<ss>sta[5];
  30. set<ss>::iterator it;
  31. ss now,list[100000],ls[100000];
  32. int cnt_list,ch,cnt_ls;
  33. struct qq
  34. {
  35. 	int id;
  36. 	double w;
  37. 	bool operator <(const qq &temp)const
  38. 	{
  39. 		return w<temp.w;
  40. 	}
  41. };
  42. struct point
  43. {
  44. 	double a,b,d;
  45. };
  46. point pt[5];
  47. struct pp
  48. {
  49. 	int id;
  50. 	double bt;
  51. };
  52. pp stk[100001],ans_list[100001];
  53. int n,num_ans;
  54. double d,c;
  55. double compute(int id,double nowt,double nowd)
  56. {
  57. 	int i,j,s,p,q,it;
  58. 	double C=0-(pt[id].b*nowt-pt[id].a*cos(nowt+pt[id].d));
  59. 	double low,high,mid;
  60. 	low=nowt;
  61. 	high=((d-nowd-C)+pt[id].a)/pt[id].b;
  62.    	for(it=0;it<=30;it++)
  63.     {
  64.        	mid=0.5*(low+high);
  65.        	if(pt[id].b*mid-pt[id].a*cos(mid+pt[id].d)+C<=d-nowd)
  66.        	     low=mid;
  67.    	    else
  68.    	        high=mid;
  69.     }
  70.     return 0.5*(low+high);
  71. }
  72. int main()
  73. {
  74. 	scanf("%d%lf%lf",&n,&d,&c);
  75. 	int i,j,s,p,q;
  76. 	for(i=0;i<n;i++)
  77. 	{
  78. 		scanf("%lf%lf%lf",&pt[i].a,&pt[i].b,&pt[i].d);
  79. 	    sta[i].clear();
  80. 	}
  81. 	now.nowd=0;
  82. 	now.nowt=0;
  83. 	now.bt=0;
  84.     now.id=0;
  85. 	sta[0].insert(now);
  86. 	double nowt,nowd;
  87. 	ans=inf;
  88. 	cnt_list=0;
  89. 	while(true)
  90. 	{
  91. 		double in=inf;
  92. 		int id;
  93. 		for(i=0;i<n;i++)
  94. 		{
  95. 			if(sta[i].size()>0)
  96. 			{
  97. 				it=sta[i].begin();
  98. 				if(in>it->nowt)
  99. 				{
  100. 				    id=i;
  101. 				    in=it->nowt;
  102. 				}
  103. 			}
  104. 		}
  105. 		if(in==inf)
  106. 		    break; 
  107. 		it=sta[id].begin();
  108. 		list[cnt_list++]=*it;
  109. 		nowt=it->nowt;
  110. 		nowd=it->nowd;
  111. 		sta[id].erase(*it);
  112. 		double vl=compute(id,nowt,nowd);
  113. 		if(ans>vl)
  114. 		{
  115. 			ch=cnt_list-1;
  116. 		    ans=vl;
  117. 		}
  118. 		if(it->nowt>ans)
  119.            break;
  120. 		int kmin,k;
  121.    	    for(s=0;s<n;s++)
  122.         {
  123.         	i=id;
  124.             j=s;
  125.             if(j==i)
  126.                continue;
  127.       	    double A,B,alpha,aa,bb,nt,nd;
  128. 	     	A=pt[i].b-pt[j].b;
  129. 	        aa=pt[i].a*cos(pt[i].d)-pt[j].a*cos(c*abs(i-j)+pt[j].d);
  130. 	        bb=pt[i].a*sin(pt[i].d)-pt[j].a*sin(c*abs(i-j)+pt[j].d);
  131. 	        B=sqrt(aa*aa+bb*bb);
  132. 	        alpha=atan2(aa,bb);
  133. 	        if(aa==0&&bb==0&&A>=eps)
  134. 	            continue;
  135. 		    	double vv=-A/B;
  136.                 if(vv<-1)
  137.                    vv=-1;
  138.                 if(vv>1)
  139.                    vv=1;
  140.                 vv=acos(vv);
  141.                 kmin=(int)((nowt-alpha-vv)/(2*pi));
  142.                 while(2*pi*kmin+vv<nowt-alpha-eps)
  143.                    kmin++; 
  144.         	    for(k=kmin-1;k<=kmin+25;k++)
  145.            	    {
  146. 			        nt=2*k*pi+vv+alpha+c*abs(i-j);
  147. 		        	if(k==kmin-1&&pt[i].b+pt[i].a*sin(nowt+pt[i].d)<pt[j].b+pt[j].a*sin(nowt+c*abs(i-j)+pt[j].d))
  148. 		    	        nt=nowt+c*abs(i-j);
  149. 			    	else if(k==kmin-1)
  150. 			    	    continue;
  151. 					nd=nowd+pt[i].b*(nt-c*abs(i-j)-nowt)-pt[i].a*cos(nt-c*abs(i-j)+pt[i].d)+pt[i].a*cos(nowt+pt[i].d);
  152.                     if(nd>=d||nt>=ans)
  153.                         break;
  154. 				    if(nd<=d)
  155.                     {
  156. 		                now.nowd=nd;
  157. 		                now.nowt=nt; 
  158. 		                now.bt=nt-c*abs(i-j);
  159. 		                now.pa=cnt_list-1;
  160.   		                now.id=j;
  161.                         if(now.nowt<ans-eps)
  162.                         {
  163. 				            double lt,rt,ld,rd,bd;
  164. 				            cnt_ls=0;
  165. 				            for(it=sta[j].lower_bound(now);it!=sta[j].end();it++)
  166. 				            {
  167.    					            lt=now.nowt;
  168.    					            ld=now.nowd;
  169.    					            rt=it->nowt;
  170.    		     			        rd=it->nowd;
  171.       				  	        bd=pt[j].b*(rt-lt)-pt[j].a*cos(rt+pt[j].d)+pt[j].a*cos(lt+pt[j].d);
  172.    				                if(ld+bd>=rd-eps)
  173.   					 	           ls[cnt_ls++]=*it;
  174. 					            else
  175. 		   	                        break;
  176. 				            }
  177. 				            for(q=0;q<cnt_ls;q++)
  178. 				               sta[j].erase(ls[q]);
  179.      	  			        it=sta[j].find(now);
  180. 				            if(it!=sta[j].end())
  181. 				                break;
  182. 							sta[j].insert(now);
  183.                         }
  184.                     }
  185. 			}
  186. 		}
  187. 	}
  188. 	printf("%.20f\n",ans);
  189. 	num_ans=0;
  190. 	while(ch!=0)
  191. 	{
  192. 		ans_list[num_ans].id=list[ch].id;
  193. 		ans_list[num_ans++].bt=list[ch].bt;
  194. 	    ch=list[ch].pa;
  195. 	}
  196. 	printf("%d\n",num_ans);
  197. 	for(i=num_ans-1;i>=0;i--)
  198. 	    printf("%d %.20f\n",ans_list[i].id+1,ans_list[i].bt);
  199. 	return 0;
  200. }
Success #stdin #stdout 0s 25432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000.00000000000000000000
0
https://ideone.com/oVvzQP
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!