首页 > ACM题库 > HDU-杭电 > HDU 3895-Find the Circle-数学相关-[解题报告]HOJ
2015
04-13

HDU 3895-Find the Circle-数学相关-[解题报告]HOJ

Find the Circle

问题描述 :

Given three circles (center of them are not co-linear), your job is to find a circle that is tangent with all these three circles. However, the circle might be not unique, as they can be either externally or internally tangent to each other. To make it clearer, you have to give the answer in some specific model. For example, you might be asked to give a circle which should be internally tangent with circle 1 and circle 2, while externally tangent with circle 3.

输入:

The first line of input contains an integer n, which is the number of test cases. Each case have three lines, each have four integers x, y, r, m. (0 <= x, y <= 10000 and 0 <= r <= 500), where x, y is position of one circle, and r is the radius. m represents the model of circle you should give. m = 0 means your circle should internally tangent with this circle, and m = 1 for externally case.

输出:

The first line of input contains an integer n, which is the number of test cases. Each case have three lines, each have four integers x, y, r, m. (0 <= x, y <= 10000 and 0 <= r <= 500), where x, y is position of one circle, and r is the radius. m represents the model of circle you should give. m = 0 means your circle should internally tangent with this circle, and m = 1 for externally case.

样例输入:

2
1 3 2 0
0 1 5 0
1 0 1 0
3 5 20 1
2 1 1 1
4 4 1 1

样例输出:

-0.4904 2.2264 3.6792
NO SOLUTION!

Problem Description
When people drink some tea in the teahouse, they also play some casual games. Now, inverting cups is a popular game. The meaning of the question is, now there are some cups which are upturned, we can regard the total number of the cups as a positive integer
number A , and we can invert some cups, the number is B and B is also a positive integer number. We define one retroflexion that if the original cup is upturned, one retroflexion makes it downward, and if the original cup is downward, one retroflexion makes
it upturned. So the question is if the whole original cups are upturned , can we invert these cups to make all the cups downward? And if it is possible, how many is the least of times?
 

Input
The input contains multiple test cases(cases<=100000). Each case one line given two numbers , the first integer A (1<=A<=2^63) and the second integer B (1<=B<=A). The input is terminated by the end of file.
 

Output
For each test case, you should output how many the least of times if it is possible for us to invert all the cups, and if it is impossible please output “No Solution!”
 

Sample Input
5 3 14 4 8 5 11 4
 

Sample Output
3 4 4 No Solution!

//

#include<iostream>
#include<cstdio>
using namespace std;
int main() {
    __int64 a, b, t, ans;
    while (scanf("%I64d%I64d",&a,&b)==2) {
        ans = 0;
        if (a % 2 && b % 2 == 0) {
            printf("No Solution!\n");
            continue;
        }
        while (1) {
                if (a / b >= 3) {
                t = (a-2*b)/b;
                ans += t;
                a -= t*b;
            }
            if (a % b == 0)ans += a / b;
            else if (a % 2 == b % 2)ans += 3;
            else if (a / b >= 2)ans += 4;
            else {
                b = a – b;
                continue;
            }
            break;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/kongming_acm/article/details/6685797


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!