fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const long double PI = acos((long double)-1.0);
  6. const long double EPS = 1e-8;
  7. const long double INF = 1e18 + 10;
  8.  
  9. struct Vector {
  10.     long double x, y;
  11.     Vector(long double _x = 0, long double _y = 0) {
  12.         x = _x;
  13.         y = _y;
  14.     }
  15.     Vector operator + (Vector v) {
  16.         return {x + v.x, y + v.y};
  17.     }
  18.     Vector operator - (Vector v) {
  19.         return {x - v.x, y - v.y};
  20.     }
  21.     Vector operator * (long double k) {
  22.         return {x * k, y * k};
  23.     }
  24.     Vector operator / (long double k) {
  25.         return {x / k, y / k};
  26.     }
  27.     void setLengthAngle(long double length, long double theta) {
  28.         x = length * cos(theta);
  29.         y = length * sin(theta);
  30.     }
  31.     long double getLength() {
  32.         return sqrt(x * x + y * y);
  33.     }
  34.     long double getLengthSquare() {
  35.         return x * x + y * y;
  36.     }
  37.     long double getAngle() {
  38.         return atan2(y, x);
  39.     }
  40.     long double cross(Vector v) {
  41.         return x * v.y - y * v.x;
  42.     }
  43.     long double dot(Vector v) {
  44.         return x * v.x + y * v.y;
  45.     }
  46.     Vector rotate(long double theta) {
  47.         return {x * cos(theta) - y * sin(theta), x * sin(theta) + y * cos(theta)};
  48.     }
  49.     long double distance(Vector v) {
  50.         return sqrt((v.x - x) * (v.x - x) + (v.y - y) * (v.y - y));
  51.     }
  52.     long double distanceSquare(Vector v) {
  53.         return (v.x - x) * (v.x - x) + (v.y - y) * (v.y - y);
  54.     }
  55. };
  56.  
  57. typedef Vector Point;
  58. typedef pair<Point, Point> Segment;
  59.  
  60. struct Ball {
  61.     Point center;
  62.     long double radius;
  63.     Vector velocity;
  64.     Ball(Point _center, Vector _velocity, long double _radius = 0) {
  65.         center = _center;
  66.         radius = _radius;
  67.         velocity = _velocity;
  68.     }
  69.     Ball(long double _radius = 0) {
  70.         radius = _radius;
  71.     }
  72.     long double getArea() {
  73.         return PI * radius * radius;
  74.     }
  75. };
  76.  
  77. typedef pair<long double, long double> TimeSegment;
  78. typedef pair<TimeSegment, Ball> TimeSegmentBall;
  79.  
  80. Vector reflect(Vector v, Segment wall) {
  81.     Vector n = (wall.second - wall.first).rotate(PI / 2.0);
  82.     n = n / n.getLength();
  83.     return v - n * (2 * n.dot(v));
  84. }
  85.  
  86. long double gd(long double x1,long double y1,long double x2,long double y2)
  87. {
  88.     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
  89. }
  90.  
  91. long double solve_cos(long double a,long double b,long double c)
  92. {
  93.     return acos((a*a+b*b-c*c)/(2*a*b));
  94. }
  95.  
  96. long double cut(long double ang,long double r)
  97. {
  98.     long double s1,s2;
  99.     s1=ang*r*r/2;
  100.     s2=sin(ang)*r*r/2;
  101.     return s1-s2;
  102. }
  103.  
  104. long double solve(long double x1 , long double y1 , long double r1 , long double x2 , long double y2 , long double r2)
  105. {
  106.     if (r1<r2)
  107.     {
  108.         swap(x1,x2);
  109.         swap(y1,y2);
  110.         swap(r1,r2);
  111.     }
  112.     long double cd=gd(x1,y1,x2,y2);
  113.     if (cd+r2<=r1+EPS)
  114.         return r2*r2*PI;
  115.     if (cd>=r1+r2-EPS)
  116.         return 0;
  117.     long double ang1=solve_cos(cd,r1,r2);
  118.     long double ang2=solve_cos(cd,r2,r1);
  119.     return cut(ang1*2,r1)+cut(ang2*2,r2);
  120. }
  121.  
  122. long double commonArea(Ball c1, Ball c2) {
  123.    return solve(c1.center.x, c1.center.y, c1.radius, c2.center.x, c2.center.y, c2.radius);
  124. }
  125.  
  126. int sign(long double x) {
  127.     if (x < EPS && x > -EPS)
  128.         return 0;
  129.     if (x > 0)
  130.         return 1;
  131.     if (x < 0)
  132.         return -1;
  133. }
  134.  
  135. Ball moveBall(Ball ball, long double deltaTime) {
  136.     return Ball(ball.center + ball.velocity * deltaTime, ball.velocity, ball.radius);
  137. }
  138.  
  139. Ball moveBall(Ball ball, TimeSegment timeSegment, long double time) {
  140.     if (time >= timeSegment.second)
  141.         return Ball(ball.center + (ball.velocity * (timeSegment.second - timeSegment.first)), ball.velocity, ball.radius);
  142.     if (time <= timeSegment.first)
  143.         return ball;
  144.     return Ball(ball.center + (ball.velocity * (time - timeSegment.first)), ball.velocity, ball.radius);
  145. }
  146.  
  147. long double maximumCommonArea(Ball ball1, Ball ball2, TimeSegment timeSegment1, TimeSegment timeSegment2) {
  148.     if (timeSegment1.first > timeSegment1.second) {
  149.         swap(timeSegment1.first, timeSegment1.second);
  150.     }
  151.     if (timeSegment2.first > timeSegment2.second) {
  152.         swap(timeSegment2.first, timeSegment2.second);
  153.     }
  154.     long double lo = max(timeSegment1.first, timeSegment2.first);
  155.     long double hi = min(timeSegment1.second, timeSegment2.second);
  156.     if (lo > hi)
  157.         return 0;
  158.     long double ret = 0;
  159.     for (int i = 0; i < 2000; i++) {
  160.         long double mid1 = (2 * lo + hi) / 3;
  161.         long double mid2 = (lo + 2 * hi) / 3;
  162.         Ball ball1mid1 = moveBall(ball1, timeSegment1, mid1);
  163.         Ball ball2mid1 = moveBall(ball2, timeSegment2, mid1);
  164.         Ball ball1mid2 = moveBall(ball1, timeSegment1, mid2);
  165.         Ball ball2mid2 = moveBall(ball2, timeSegment2, mid2);
  166.         if ((ball1mid1.center - ball2mid1.center).getLength() >= (ball1mid2.center - ball2mid2.center).getLength())
  167.             lo = mid1;
  168.         else
  169.             hi = mid2;
  170.     }
  171.     Ball newBall1 = moveBall(ball1, timeSegment1, lo);
  172.     Ball newBall2 = moveBall(ball2, timeSegment2, lo);
  173.     return commonArea(newBall1, newBall2);
  174. }
  175.  
  176. long double segmentPointDistance(Segment segment, Point point) {
  177.     return (segment.first - point).cross(segment.second - point) / (segment.second - segment.first).getLength();
  178. }
  179.  
  180. vector<TimeSegmentBall> getTimeSegmentBalls(Ball ball, Segment wall) {
  181.     int dir1 = sign((wall.first - ball.center).cross(wall.second - ball.center));
  182.     int dir2 = sign((wall.first - moveBall(ball, INF).center).cross(wall.second - moveBall(ball, INF).center));
  183.     if (dir1 == dir2) {
  184.         vector<TimeSegmentBall> ret;
  185.         ret.push_back({{0.0, INF}, ball});
  186.         return ret;
  187.     }
  188.     long double lo = 0, hi = INF;
  189.     for (int i = 0; i < 2000; i++) {
  190.         long double mid = (lo + hi) / 2.0;
  191.         Ball ballMid = moveBall(ball, mid);
  192.         long double dis = segmentPointDistance(wall, ballMid.center);
  193.         if (sign(dis) != dir1 || (sign(dis) == dir1 && fabs(dis) < ball.radius))
  194.             hi = mid;
  195.         else
  196.             lo = mid;
  197.     }
  198.     vector<TimeSegmentBall> ret;
  199.     ret.push_back({{0.0, lo}, ball});
  200.     ball = moveBall(ball, lo);
  201.     ball.velocity = reflect(ball.velocity, wall);
  202.     ret.push_back({{hi, INF}, ball});
  203.     return ret;
  204. }
  205.  
  206. int tc;
  207. vector<TimeSegmentBall> timeSegmentBalls[10];
  208.  
  209. int main() {
  210.     cin >> tc;
  211.     cout.precision(12);
  212.     while (tc--) {
  213.         vector<Ball> balls;
  214.         for (int i = 0; i < 2; i++) {
  215.             long double x, y;
  216.             long double vx, vy;
  217.             long double r;
  218.             cin >> x >> y;
  219.             cin >> vx >> vy;
  220.             cin >> r;
  221.             balls.push_back(Ball(Point(x, y), Vector(vx, vy), r));
  222.         }
  223.         long double wallX1, wallY1;
  224.         long double wallX2, wallY2;
  225.         cin >> wallX1 >> wallY1;
  226.         cin >> wallX2 >> wallY2;
  227.         Segment wall(Point(wallX1, wallY1), Point(wallX2, wallY2));
  228.         long double ans = 0;
  229.         for (int i = 0; i < 2; i++) {
  230.             timeSegmentBalls[i] = getTimeSegmentBalls(balls[i], wall);
  231.         }
  232.         for (auto timeSegmentBall0: timeSegmentBalls[0])
  233.             for (auto timeSegmentBall1: timeSegmentBalls[1]) {
  234.                 ans = max(ans, maximumCommonArea(timeSegmentBall0.second, timeSegmentBall1.second, timeSegmentBall0.first, timeSegmentBall1.first));
  235.             }
  236.         cout << fixed << ans << endl;
  237.     }
  238.     return 0;
  239. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lRwdZO
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!