Problem B
Probability Through experiment
Time Limit: 2 seconds
Mathematicians have often solved
problems by just doing some simulation or experiments. For example, the value
of pi (p) can be approximately
determined by randomly plotting points in a square that inscribes a circle.
Because if the square is a 250x250 square, then its area is 62500 and the area
of the inscribed circle is pi*1252=15625pi. As the points are
plotted randomly, so it can be assumed that number of points inside the circle
and total number points plotted in the square is proportional to their
respective area. So, in this way, the value of pi can approximately be
determined by counting how many points are inside the circle (Figure 1). The
value of pi can even be determined using a more sophisticated experiment like
the Buffon’s needle experiment (Figure 2).
|
|
|
Figure 1: Pi
approximation by counting the number of points inside the circle
|
|
|
|
Figure 2: Buffon’s
needle experiment
|
The two experiments mentioned
above to approximately determine the value of pi could be simulated by writing
a computer program very easily. It would have been nice to do this sort of
experiment a lot of time (Say 1 billion billion) and get an almost perfect
result but for lack of time we cannot do that in real life. In this problem,
you will have to write a program that will help Professor Wu to perform a
similar sort of experiment but this program may not be that straightforward.
Professor Neal Wu is trying to
solve a classic problem using simulation: If three points are randomly plotted
on the boundary of a circle, then what is the probability that they will be the
three vertex of an acute triangle? Of course, this problem can be solved
analytically and the result he gets is 0.25. Now, he wants to verify this
result through an experiment. The result can be found approximately by plotting
three random points on a circle billions of times and counting how many times
these three points form an acute triangle. The beauty of such an experiment (as
mentioned above) is that if we increase the number of trials, the result will
become even more accurate. But if Dr. Wu wants to repeat this process 1000
billion times, it will take 2 hours of time and if he wants to repeat it a
billion billion times, it may take more than 200
years. Dr. Wu has discovered that this process can be sped up by using a
different approach – generate n random points on the
boundary of a circle and they form 
triangles
as vertices. How many of these triangles are acute triangles? If the number of
acute triangle is M and let N = ,
then the desired probability is 
.
So, given the n points on the boundary, you have to assist Dr. Wu by writing a
very efficient program to find the number of acute triangles.
|
|
|
Figure 3:
Example of a circle with given points on the boundary
|
Input
The input file contains around 40
test cases. But most of the cases are not extreme, so the size of the input
file is around 3 MB. The description of each test case is given below:
Each case starts with two
positive integers n (0 < n ≤ 20000) and r (0 < r ≤ 500).
Here, n is the total of points on the circle boundary and r is the radius of
the circle. The center of the circle is always at the origin (0,0). Each of the next N lines denotes the location of one
point on the boundary of the circle. Each point is P, denoted by a
floating-point number θ (0.000 ≤ θ < 360.000). This θ
is actually the angle (expressed in degree) the point P creates at the center
of the circle with the positive direction of x-axis. So the Cartesian
coordinate of P is ( r*cos(θ),
r*sin(θ)). Value of θ will always have exactly three digits after the
decimal point. No two points will be at the same
location.
A line containing two zeroes terminates the input. This line
should not be processed.
Output
Each test case produces one line
of output. This line contains the serial of output followed by an integer. This
integer denotes how many of the triangles formed by these n points are actually acute
triangles.
/* 20000 points generated on the
boundary of a circle can actually create 20000*19999*19998/6 ~1333 billion
triangles. So, of experiment for 1333 billions can be
done in, say, 0.5 second. Then experiments with 1 billion billion
triangles can be done in around 100 hours only (In contrast to 200 years
mentioned earlier) just by repeating this experiment. Also, if we put 1817120
points on the boundary of the circle, around 1 billion billion
triangles are created, and the number of acute triangles within this large
number of triangles can be computed within 5 minutes. */
|
Sample
Input
|
Sample Output
|
|
4 71
234.600
33.576
20.375
84.908
7 7
11.586
114.435
248.411
108.640
287.629
150.224
340.481
0 0
|
Case
1: 2
Case
2: 12
|
這題前面給了很多數學知識，不過真正要你求的是，圓周上有很多點，任取三點做三角形，有多少個銳角(acute)三角形，銳角不包括直角(right)三角形。
我代碼中好像打成 normal 了，請多多見諒。
那很簡單，找出所有畫分圓的直徑，然後抓兩個點(同一側)跟直徑上的點配成鈍角，直角我這邊是特別判斷的。
直角測資。
3 5
0.000
30.000
180.000
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
int x[20005];
inline int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int n, r, i, j, a, b;
int cases = 0;
while(scanf("%d %d", &n, &r) == 2) {
if(n == 0) break;
for(i = 0; i < n; i++) {
ReadInt(&a);
ReadInt(&b);
x[i] = a*1000+b;
}
sort(x, x+n);
long long tot = 0, t1, t2, normal = 0, ans;
ans = (long long)n*(n-1)*(n-2)/6;
queue<int> Q;
for(i = 0, j = 0; i < n; i++) {
if(x[i] >= 180000) break;
while(j < n && x[j] <= x[i]+180000)
Q.push(x[j]), j++;
while(!Q.empty() && Q.front() <= x[i]) Q.pop();
t1 = Q.size();
t2 = n-1-t1;
if(j > 0 && x[j-1] == x[i]+180000)
t1--, normal += t1+t2;
tot += t1*(t1-1)/2;
tot += t2*(t2-1)/2;
}
for(i = 0; i < n; i++) {
x[i] += 180000;
if(x[i] >= 360000) x[i] -= 360000;
}
sort(x, x+n);
while(!Q.empty()) Q.pop();
for(i = 0, j = 0; i < n; i++) {
if(x[i] >= 180000) break;
while(j < n && x[j] <= x[i]+180000)
Q.push(x[j]), j++;
while(!Q.empty() && Q.front() <= x[i]) Q.pop();
t1 = Q.size();
t2 = n-1-t1;
if(j > 0 && x[j-1] == x[i]+180000)
t1--, normal += t1+t2;
tot += t1*(t1-1)/2;
tot += t2*(t2-1)/2;
}
printf("Case %d: %lld\n", ++cases, ans-tot/2-normal/2);
}
return 0;
}
