[UVA][二分] 10649 - Danger Point
Danger Point
Input: standard input
Output: standard output
Time Limit: 1 second
Jamal and Kamal were two friends. They were renowned for their friendship in their area. Once Jamal lend a big amount from Kamal and didn’t back that within time. At first Kamal didn’t say anything to Jamal but after few days when he understood that he was not going to give his money, he became rough on him. And the result is they are now enemies to each other. After 3 months there came another two friends to live, Rahim and Karim. Their houses stood such a way that the lines connecting Jamal's and Kamal's houses with Rahim areperpendicular; the same applies to Karim. Not only this, the line joining Rahim and Karim’s houses madeangle ‘Pi/4’ radians with the line joining Jamal and Kamal’s houses. Intersection of both of the joining lines was known as “Danger Point”. Know why? Same thing happened with Rahim and Karim! Money had done the damage in their friendship and when the four meet, surprisingly it is in that “Danger Point”, there arise a long quarrel. And others feel really annoyed with them. So, you a good programmer and neighbor of them decided to discontinue this situation. To solve this main problem, first you have to solve a little problem: Find out the distance of Rahim or Karim’s house from the “Danger Point”.
Input
You know the two data only, the distance between Jamal and Kamal’s house, and one distance from “Danger Point” to Rahim or Karim’s house. And you know you will stop when you find both of them zero. That is they will stay together.
Output
Output is a single-lined single value (6 digits after the decimal point) representing distance from “Danger Point” to Rahim or Karim’s house (other one's without the given one) for correct input set and for incorrect input set just print "INCORRECTINFORMATION !!!".
Sample Input
333.25 101.154
50.50 10.10
10.10 50.50
0 0
Sample Output
212.827746
34.250766
INCORRECT INFORMATION !!!
Problem setter: Enamul HaqueThanks to Derek Kisman for his alternate solution.
“It takes two to make a quarrel - it's clear two is the lower limit here, but the upper limit is unknown to me :)”
題目描述：
Jamal 與 Kamal 位在圓直徑上的兩端, Karim 與 Rahim 是圓上的兩點,
這兩點連線會與直徑交一點 D (Danger Point), D 與 Karim 的距離會給你,
求 D 到 Rahim 的距離。
題目解法：
說實在, 直接計算有點繁瑣。
另這圓心 (0, 0) => x*x + y*y = r*r
而這條直線是 y = -x + b
交圓有兩點, 取左側的點為 Karim 的所在, 二分查找 b 得答案,
然後就可以直接算點的距離了
#include <stdio.h>
#include <math.h>
int main() {
double R, a;
while(scanf("%lf %lf", &R, &a) == 2) {
if(R == 0) break;
double r = R/2;
double low = -r, upp = r, b;
double cnt = 0, tmp;
double x, y;
if(r*r*2 < a*a) {
puts("INCORRECT INFORMATION !!!");
continue;
}
while(cnt <= 50 && low <= upp) {
b = (low+upp)/2;
x = (2*b - sqrt(8*r*r-4*b*b))/4;
y = (-x) + b;
tmp = hypot(x-b, y);
if(tmp < a)
low = b;
else
upp = b;
cnt++;
}
x = (2*b + sqrt(8*r*r-4*b*b))/4;
y = (-x) + b;
printf("%.6lf\n", hypot(x-b, y));
}
return 0;
}