fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define  double   long double
  5. #define eps 1e-16
  6. #define M_PI 3.141592653589793
  7. using namespace std;
  8.  
  9. double X1,Y1,X2,Y2,Vx1,Vx2,Vy1,Vy2,r1,r2,Wx1,Wy1,Wx2,Wy2;
  10.  
  11. struct PT {
  12.   double x, y;
  13.   PT() {}
  14.   PT(double x, double y) : x(x), y(y) {}
  15.   PT(const PT &p) : x(p.x), y(p.y)    {}
  16.   PT operator + (const PT &p)  const { return PT(x+p.x, y+p.y); }
  17.   PT operator - (const PT &p)  const { return PT(x-p.x, y-p.y); }
  18.   PT operator * (double c)     const { return PT(x*c,   y*c  ); }
  19.   PT operator / (double c)     const { return PT(x/c,   y/c  ); }
  20. };
  21.  
  22. double dot(PT p, PT q){ return p.x*q.x+p.y*q.y; }
  23.  
  24.  
  25. PT ProjectPointLine(PT a, PT b, PT c) {
  26.   return a + (b-a)*dot(c-a, b-a)/dot(b-a, b-a);
  27. }
  28.  
  29.  
  30.   double gd(  double x1,  double y1,  double x2,  double y2)
  31. {
  32. 	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
  33. }
  34.  
  35.   double solve_cos(  double a,  double b,  double c)
  36. {
  37. 	return acos((a*a+b*b-c*c)/(2*a*b));
  38. }
  39.  
  40.   double cut(  double ang,  double r)
  41. {
  42. 	  double s1,s2;
  43. 	s1=ang*r*r/2;
  44. 	s2=sin(ang)*r*r/2;
  45. 	return s1-s2;
  46. }
  47.  
  48.   double solve(  double x1 ,   double y1 ,   double r1 ,   double x2 ,   double y2 ,   double r2)
  49. {
  50. 	if (r1<r2)
  51. 	{
  52. 		swap(x1,x2);
  53. 		swap(y1,y2);
  54. 		swap(r1,r2);
  55. 	}
  56. 	  double cd=gd(x1,y1,x2,y2);
  57. 	if (cd+r2<=r1+eps)
  58. 		return r2*r2*M_PI;
  59. 	if (cd>=r1+r2-eps)
  60. 		return 0;
  61. 	  double ang1=solve_cos(cd,r1,r2);
  62. 	  double ang2=solve_cos(cd,r2,r1);
  63. 	return cut(ang1*2,r1)+cut(ang2*2,r2);
  64. }
  65.  
  66. double cross(double Ax,double Ay,double Bx, double By){
  67.     return Ax * By - Ay * Bx;
  68. }
  69. double dot(double Ax,double Ay,double Bx, double By){
  70.     return Ax * Bx + Ay * By;
  71. }
  72. double area(double r1,double r2,double d){
  73.  
  74.     return solve(0,0,r1,0,d,r2);
  75. }
  76. double solveWall()
  77. {
  78.     double seg = hypot(Wx1-Wx2,Wy1-Wy2);
  79.     double disFromWall = fabs(cross(Wx1-Wx2,Wy1-Wy2,X1-Wx1,Y1-Wy1))/seg;
  80.     return 0;
  81. }
  82.  
  83. PT getNazeer(PT lineA,PT lineB,PT c,double r){
  84.      PT zbr = ProjectPointLine(lineA,lineB,c);
  85.      PT u = (zbr - c)/sqrt(dot(zbr-c,zbr-c));
  86.  
  87.      u = u * r;
  88.      return  (zbr-u - c)+(zbr - u- c) + c;
  89. }
  90. double getTime(PT lineA,PT lineB,PT c,double r,double Vx,double Vy){
  91.      PT zbr = ProjectPointLine(lineA,lineB,c);
  92.      double Dist = sqrt(dot(zbr-c,zbr-c));
  93.      PT u = (zbr - c)/Dist; /// unit vector
  94.      PT nig = PT(Vx,Vy);
  95.      PT R = u * r;
  96.      double projV  = dot(nig, u);
  97.      if(projV <= 0)
  98.          return 1e9;
  99.      double Time = sqrt(dot((zbr-R - c),(zbr - R- c)))/projV;
  100.      return  Time;
  101. }
  102. double solve() {
  103.  
  104.  
  105.     double rVx = -Vx1 + Vx2,rVy = -Vy1+Vy2;
  106.     double deltaX = X1 - X2, deltaY = Y1 - Y2;
  107.     double zbr = dot(rVx,rVy,deltaX,deltaY);
  108.     double initialRes = area(r1,r2,hypot(deltaX,deltaY));
  109.  
  110.     if(zbr < 0)
  111.         return max(initialRes,solveWall());
  112.     double zinj = cross(rVx,rVy,deltaX,deltaY);
  113.     if(rVx == rVy && rVy == 0){
  114.         zinj = hypot(deltaX,deltaY);
  115.     }
  116.     else
  117.         zinj /= hypot(rVx,rVy);
  118.     zinj = fabs(zinj);
  119.     if(zinj > r1 + r2)
  120.         return max(initialRes,solveWall());
  121.     return max(solveWall(),max(area(r1,r2,zinj),initialRes));
  122.  
  123. }
  124. int main() {
  125. #ifdef __Jafar
  126.     freopen("input.txt", "r", stdin);
  127.  
  128. #else
  129. #endif
  130.    // freopen("out.out","w",stdout);
  131.     int t;cin>>t;
  132.     int j = 0;
  133.     while(t--) {
  134.         cout << fixed;
  135.         cout.precision(12);
  136.         cin >> X1 >> Y1 >> Vx1 >> Vy1 >> r1 >> X2 >> Y2 >> Vx2 >> Vy2 >> r2;
  137.  
  138.         cin >> Wx1 >> Wy1 >> Wx2 >> Wy2;
  139.         j++;/*
  140.         if(j==90){
  141.             cout<<X1<<' ' << Y1<<endl<<Vx1<<' '<<Vy1<<endl<<r1<<endl<<X2<<' '<<Y2<<endl<<Vx2<<' '<<Vy2<<endl<<r2<<endl<<Wx1<<' '<<Wy1<<endl<<Wx2<<' '<<Wy2<<endl;
  142.             return 0;
  143.         }*/
  144.         if (r1 > r2) {
  145.             swap(r1, r2);
  146.             swap(X1, X2);
  147.             swap(Y1, Y2);
  148.             swap(Vx1, Vx2);
  149.             swap(Vy1, Vy2);
  150.         }
  151.         double res = solve();
  152.         PT zbr = getNazeer(PT(Wx1, Wy1), PT(Wx2, Wy2), PT(X1, Y1), r1);
  153.         double t1 = getTime(PT(Wx1, Wy1), PT(Wx2, Wy2), PT(X1, Y1), r1, Vx1, Vy1),
  154.         t2 = getTime(PT(Wx1, Wy1), PT(Wx2, Wy2), PT(X2, Y2), r2, Vx2, Vy2);
  155.         /// zbr نظير
  156.         if (t1 > t2) {
  157.             swap(t1,t2);
  158.             swap(r1, r2);
  159.             swap(X1, X2);
  160.             swap(Y1, Y2);
  161.             swap(Vx1, Vx2);
  162.             swap(Vy1, Vy2);
  163.         }
  164.        // cout<<t1<<' '<<t2<<endl;
  165.         PT newVelocity;
  166.         if (t1 != 1e9) {
  167.             //cout<<Vx1<<' '<<Vy1<<endl;
  168.             newVelocity = getNazeer(PT(Wx1, Wy1), PT(Wx2, Wy2), PT(2e6 + 7 + Vx1, 2e6 + 7 + Vy1), r1);
  169.             newVelocity = newVelocity - getNazeer(PT(Wx1, Wy1), PT(Wx2, Wy2), PT(2e6 + 7, 2e6 + 7), r1);
  170.             X1 = Vx1 * t1 + X1;
  171.             Y1 = Vy1 * t1 + Y1;
  172.             X2 = Vx2 * t1 + X2;
  173.             Y2 = Vy2 * t1 + Y2;
  174.             //cout<<X1<<' '<<Y1<<' ' <<X2<<' '<<Y2<<endl;
  175.  
  176.             double Tx = X1, Ty = Y1, tVx = Vx1, tVy = Vy1;
  177.             Vx1 = newVelocity.x;
  178.             Vy1 = newVelocity.y;
  179.             //cout<<Vx1<<' '<<Vy1<<endl;
  180.             res = max(res, solve());
  181.         }
  182.  
  183.  
  184.  
  185.  
  186.             swap(r1, r2);
  187.             swap(X1, X2);
  188.             swap(Y1, Y2);
  189.             swap(Vx1, Vx2);
  190.             swap(Vy1, Vy2);
  191.         if (t2 != 1e9&&fabs(t2-t1)>1e-9) {
  192.            newVelocity = getNazeer(PT(Wx1, Wy1), PT(Wx2, Wy2), PT(2e6+7+ Vx1,2e6+7+ Vy1), r1);
  193.             newVelocity = newVelocity - getNazeer(PT(Wx1, Wy1), PT(Wx2, Wy2),PT(2e6+7, 2e6+7), r1);
  194.             X1 = X1 + (t2 - t1) * Vx1;
  195.             Y1 = Y1 + (t2 - t1) * Vy1;
  196.             X2 = X2 + (t2 - t1) * Vx2;
  197.             Y2 = Y2 + (t2 - t1) * Vy2;
  198.             Vx1 = newVelocity.x;
  199.             Vy1 = newVelocity.y;
  200.             res = max(res, solve());
  201.         }
  202.         cout << res << endl;
  203.     }
  204.     return 0;
  205. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Nqr9Ow
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!