解題區/解題區 - UVa

UVa 10378 - Complex Numbers

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Problem

Numbers of the form a±bi are called complex numbers (Where i = √(-1)). In this problem you will have to find all the values of (a±bi)1/n.

Input

The input file contains several lines of input. Each line has two parts. The first part will contain a complex number of the form a±bi and the second part will contain an integer n (0 < n <=100). Here a and b are integer numbers and 0 <= |a|, |b|<100. Input is terminated by end of file.

Output

For each line of input you should produce n+2 lines of output. The description of output for each line of input is given in the next paragraph:

First line contains the case number as shown in the sample output. Next n lines should contain the n-th roots of the input complex number. The printed complex numbers should be of the form x±yi, where x and y are floating point numbers rounded upto three digits after the decimal point. Note that there is no space between the operators and operands. The roots are sorted according to descending order of their real part and then according to the descending order of their imaginary part. When the printed value of x or y is 0.000, it should be interpreted as positive zero. So you should never print something like “-0.000”. After all these outputs print a blank line.

Sample Input

1
2
3+4i 2
5-4i 3

Sample Output

1
2
3
4
5
6
7
8
Case 1:
2.000+1.000i
-2.000-1.000i
Case 2:
1.810-0.414i
-0.546+1.775i
-1.264-1.361i

Solution

題目描述：

問虛數 a+bi 的 n 次根號的結果，並且根據實數由大至小、虛數由大至小的字典順序輸出。

題目解法：

先算出 a+bi 所占有的角度 theta，得到 (theta + 2 * pi * i / n) 是每一個根的角度，因為根據角度疊加原理得到 (theta + 2 * pi * i / n) ^ n = theta + 2 * pi * i ＝ theta，但是這題的困難是在於 如何避免 -0.000 的輸出。

原本錯誤排序的寫法

1
2
3
4
5
bool cmp(Point a, Point b) {
    if(fabs(a.x - b.x) > eps)
        return a.x < b.x;
    return a.y < b.y;
}

應更正為如下代碼，如果要問我為什麼，現在還沒有仔細地理解，照理來說應該是差不多的。

1
2
3
4
5
6
7
bool cmp(Point a, Point b) {
    if(fabs(a.x - b.x) > eps)
        return a.x < b.x;
    if(fabs(a.y - b.y) > eps)
        return a.y < b.y;
    return false;
}

之前是想利用 sprintf(buffer, "%+.3lf%+.3lf", a, b); 去檢查 +0.000 和 -0.000，這種寫法有點太過了，不過應該也是可行的。

lang: cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
bool cmp(pair<double, double> a, pair<double, double> b) {
    if(fabs(a.first - b.first) > eps)
        return a.first > b.first;
    if(fabs(a.second - b.second) < eps)
        return false;
    return a.second > b.second;
}
int main() {
    char s[50];
    const double pi = acos(-1);
    int n, i, cases = 0;
    double a, b;
    while(scanf("%s %d", s, &n) == 2) {
        if(sscanf(s, "%lf+%lfi", &a, &b) == 2)
            {}
        else
            sscanf(s, "%lf-%lfi", &a, &b), b = -b;
        double theta = atan2(b, a);
        double k = pow(sqrt(a*a+b*b), 1.0/n);
        double px, py;
        pair<double, double> D[128];
        for(i = 0; i < n; i++) {
            px = k*cos((theta + i*2*pi)/n);
            py = k*sin((theta + i*2*pi)/n);
            D[i] = make_pair(px, py);
        }
        sort(D, D+n, cmp);
        printf("Case %d:\n", ++cases);
        for(i = 0; i < n; i++) {
        	if(fabs(D[i].first) < 0.0005)	D[i].first = 0;
        	if(fabs(D[i].second) < 0.0005)	D[i].second = 0;
        	printf("%.3lf%+.3lfi\n", D[i].first, D[i].second);
        }
        puts("");
    }
    return 0;
}