解題區/解題區 - UVa

UVa 10732 - The Strange Research

contents

  1. 1. Input
  2. 2. Output
  3. 3. Sample Input
  4. 4. Output for Sample Input
  5. 5. Solution

Professor A. Karim is working on a project of measuring the surface area of an unknown unearthly object. After a lot of calculation he finds that the surface area of that object is (a+b)(1-ab), where a and b are two parameters related to surface area of that object. With the help of some more advanced experiments he finds N floating-point numbers, which can be possible values of a and b. From the N numbers he can select two values for a and b in NC2 ways (Note that the selections a=2, b=3 and a=3, b=2 are considered same because (a+b)(1-ab) is equal to (b+a)(1-ba)). Karim needs to do some more expensive experiments to find out the real value of a and b, but before doing that he wants to keep only the obvious choices: the selections, which cause the surface of the object to be positive (Greater than zero). Your job is to help Prof. Karim to count how many of the NC2 selections (the value of a and b) causes (a+b)(1-ab) to be positive. Please note that your method must be efficient. (An O(N2) solution will not do)

Input

The input fine contains maximum 7 sets of inputs.

First line of each set contains an integer N (0<N<=10000). Each of the next N lines contains one floating-point number F (|F|<30000.0). The meaning of N is given in the problem statement.

The Input can have the same number twice or even more times. In such cases two same numbers should be considered different.

Input is terminated by a case where the value of N is zero. This case should not be processed.

Output

For each set of input produce one line of output. This line contains the serial no of output followed by an integer which indicates how many of the NC2 selections will cause the value of the expression (a+b)(1-ab) to be positive. Look at the output for sample input for details. You can consider any value greater than 10-15 is positive.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
5
8197.4013
-3622.8175
-1495.5118
-3958.2735
-678.2750
5
-1208.8234
1465.1943
2699.873
-6665.3587
-4344.6286
0

Output for Sample Input

1
2
Case 1: 10
Case 2: 5

Solution

題目描述：

從一堆數字中，任挑兩個實數出來，計算 (a + b) * (1 + a * b) > 1e-15 的對數有多少個。

題目解法：

固定其中一個數字 a 後，可以找到 b 的一元二次方程式，找到區間解的個數即可。
將輸入的數字排序，二分根的位置即可，但是麻煩的地方在於 > 1e-15，因此這部分做了些許的微調。

// 因為沒有考慮 1e-15 吞了不少 WA。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    int n, cases = 0;
    double v[32767];
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 0; i < n; i++)
            scanf("%lf", &v[i]);
            
        sort(v, v+n);
        int ret = 0, pos = 0;
        for(int i = 0; i < n; i++)
            if(v[i] > 0)
                pos ++;
        for(int i = 0; i < n; i++) {
            double a = -v[i], b = (1 - v[i]*v[i]), c = v[i];
            double r1, r2;
            if(b*b - 4*a*c < 0)	continue;
            if(fabs(a) < eps) {
                ret += pos;
                continue;
            }
            r1 = (-b - sqrt(b*b - 4*a*c))/2/a;
            r2 = (-b + sqrt(b*b - 4*a*c))/2/a;
            if(r1 > r2)	swap(r1, r2);
            
            int l = lower_bound(v, v + n, r1) - v;
            int r = upper_bound(v, v + n, r2) - v;
            int cnt = 0;
//			printf("%lf %lf %d %d\n", r1, r2, l, r);
            if(v[i] > 0) { // [l, r)
                while(l >= 0 && (v[l] + v[i])*(1 - v[l]*v[i]) > 1e-15)
                    l--;
                l++;
                while(l < n && (v[l] + v[i])*(1 - v[l]*v[i]) <= 1e-15)
                    l++;
                while(r < n && (v[r] + v[i])*(1 - v[r]*v[i]) > 1e-15)
                    r++;
                if(l <= i && i < r)
                    cnt--;
                cnt += r - l;
//				for(int j = 0; j < n; j++) {
//					if(j == i)	continue;
//					if(v[j] > r1 && v[j] < r2)
//						ret++;
//				}
            } else {
                while(l >= 0 && (v[l] + v[i])*(1 - v[l]*v[i]) <= 1e-15)
                    l--;
                l++;
                while(l < n && (v[l] + v[i])*(1 - v[l]*v[i]) > 1e-15)
                    l++;
                while(r < n && (v[r] + v[i])*(1 - v[r]*v[i]) <= 1e-15)
                    r++;
                if(i < l || i >= r)
                    cnt--;
                cnt += l + (n - r);
//				for(int j = 0; j < n; j++) {
//					if(j == i) 	continue;
//					if(v[j] < r1 || v[j] > r2)
//						ret++;
//				}
            }
//			int cnt2 = 0;
//			for(int j = 0; j < n; j++) {
//				if(i == j)	continue;
//				cnt2 += (v[i] + v[j]) * (1 - v[i]*v[j]) > 1e-15;
//			}
//			if(cnt != cnt2) {
//				printf("%lf %d %d %lf %lf, %lf %lf\n", v[i], cnt, cnt2, r1, r2, v[l], v[r-1]);
//				return 0;
//			}
            ret += cnt;
        }
        printf("Case %d: %d\n", ++cases, ret/2);
    }
    return 0;
}
/*
2
0
0
*/