[UVA][掃描線] 11355 - Cool Points
|
We have a circle of radius R and several line segments situated within the circumference of this circle. Let’s define a cool point to be a point on the circumference of this circle so that the line segment that is formed by this point and the centre of the circle makes no intersection with any of the given line segments.
For this problem, you have to find out the percentage of cool points from all possible points on the circumference of the given circle.
Input
The input file starts with an integer T(T<1000) that indicates the number of test cases. Each case starts with 2 integers N(0 <= N < 100) and R(0 < R < 1001). N represents the number of line segments and R represents the radius of the circle. Each of the next N lines contains 4 integers in the order x1, y1, x2 and y2. (x1, y1) – (x2, y2) represents a line segment.
You can assume that all the line segments will be inside the circle and no line segment passes through the origin. Also consider the center of the circle to be on the origin.
Output
For each input, output the case number followed by the percentage, rounded to 2 decimal places, of cool points. Look at the output for exact format.
|
Sample Input |
Output for Sample Input |
|
2 1 10 2 0 0 2 0 5 |
Case 1: 75.00% Case 2: 100.00% |
ProblemSetter: Sohel Hafiz
Special Thanks: Ivan Krasilnikov
題目描述：
以原點半徑為 R 的圓以及 N 個線段，求圓上任一點拉到圓心不相交的機率為何 ?
題目解法：
隨便考慮線段與圓的情況，不過題目好像有特別提到給定的線段一定會跟圓有交點。
如果不說的話，考慮求出線與圓之間的交點，之後再約束到線段上。
得到在圓內的線段後，再求極角區間，最後使用掃描線算法得到覆蓋的極角區間。
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
const double pi = acos(-1);
vector<pair<double, double> > getIntersection(double a, double b, double c, double R) {
// ax + by = c, x^2 + y^2 = R^2;
vector<pair<double, double> > ret;
double ta, tb, tc;
double x1, x2, y1, y2, sq;
if(fabs(b) > 1e-8) {
ta = 1 + a*a/(b*b);
tb = - 2*a*c/(b*b);
tc = c*c/(b*b) - R*R;
sq = tb*tb - 4*ta*tc;
if(sq < 0)
return ret;
sq = sqrt(sq);
x1 = (-tb + sq)/(2 * ta);
x2 = (-tb - sq)/(2 * ta);
if(fabs(x1 - x2) < 1e-8)
goto same_x;
y1 = (c - a * x1)/b;
y2 = (c - a * x2)/b;
ret.push_back(make_pair(x1, y1));
ret.push_back(make_pair(x2, y2));
} else {
x1 = x2 = c / a;
same_x:
sq = R*R - x1*x1;
if(sq < 0)
return ret;
sq = sqrt(sq);
y1 = sq, y2 = -sq;
if(fabs(sq) > 1e-8)
ret.push_back(make_pair(x1, y1));
ret.push_back(make_pair(x2, y2));
}
return ret;
}
vector<pair<double, double> > THETA;
void getInterval(double x1, double y1, double x2, double y2,
vector<pair<double, double> > I) {
if(I.size() != 2) return ;
double vx, vy, l = 0, r = 1, tl, tr;
vx = x2 - x1;
vy = y2 - y1;
tl = (I[0].first - x1) / vx;
tr = (I[1].first - x1) / vx;
if(tl > tr) swap(tl, tr);
l = max(l, tl), r = min(r, tr);
if(l > r) return ;
x2 = x1 + vx * l;
y2 = y1 + vy * l;
tl = atan2(y2, x2);
x2 = x1 + vx * r;
y2 = y1 + vy * r;
tr = atan2(y2, x2);
if(tl > tr) swap(tl, tr);
if(tr - tl >= pi) {
THETA.push_back(make_pair(-pi, tl));
THETA.push_back(make_pair(tr, pi));
} else {
THETA.push_back(make_pair(tl, tr));
}
return ;
}
int main() {
int testcase, cases = 0;
int N, R;
int i, j, k;
int x1, x2, y1, y2;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &N, &R);
THETA.clear();
for(i = 0; i < N; i++) {
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
double a, b, c;
a = y2 - y1;
b = x1 - x2;
c = a * x1 + b * y1;
vector<pair<double, double> > r = getIntersection(a, b, c, R);
getInterval(x1, y1, x2, y2, r);
}
sort(THETA.begin(), THETA.end());
double cover = 0;
for(i = 0; i < THETA.size(); ) {
double l = THETA[i].first, r = THETA[i].second;
i++;
while(i < THETA.size() && THETA[i].first < r) {
r = max(r, THETA[i].second);
i++;
}
cover += r - l;
}
printf("Case %d: %.2lf%%\n", ++cases, (2*pi - cover)*100 / (2*pi));
}
return 0;
}
/*
1
5 10
-5 4 -7 -9
5 -2 -5 7
4 -6 2 -10
9 -3 3 -8
-4 -8 5 3
2
1 10
2 0 0 2
0 5
*/