Search on the blog

2012年12月29日土曜日

Codeforces Round #152 Robo-Footballer

Problem Statement
A robot is playing soccer. To get a point, the robot shoots the ball in a way that the ball bounces off the wall once and goes into the goal net. If the ball touches goal posts or the wall more than once, it is caught by the opponent's goal keeper. The ball is considered to touch another object if the distance between the object and the center of the ball is less than the radius of the ball. Can the robot make the goal? If so, print the coordinates of the point the robot aims at.

Approach
Look at the figure below. It's self-explaining. The key techniques are:
  1. not consider the reflection -- just go through the wall! --
  2. consider only the "edge" case where the ball almost touches a goal post.


Source Code
#include <iostream>
#include <cstdio>
#include <complex>

using namespace std;

#define EPS (1e-8)
typedef complex<double> point;

double cross(point a, point b) {
    return a.real() * b.imag() - a.imag() * b.real();
}

double distanceLnPt(point a, point b, point c) {
    return abs(cross(b-a, c-a)) / abs(b-a);
}

point intersectionLn(point a1, point a2, point b1, point b2) {
    point a = a2 - a1;
    point b = b2 - b1;
    return a1 + a * cross(b, b1-a1) / cross(b, a);
}

int main() {
    int y1, y2, yw, xb, yb, r;

    cin >> y1 >> y2 >> yw >> xb >> yb >> r;

    yw -= r;
    point a(xb, yb);
    point b(0, 2*yw-(y1+r));
    point c(0, 2*yw-y2);

    double d = distanceLnPt(a, b, c);
    point pw = intersectionLn(a, b, point(0, yw), point(1, yw));

    if (d + EPS > r)
        printf("%.18lf", pw.real());
    else
        puts("-1");

    return 0;
}

0 件のコメント:

コメントを投稿