[UVA][掃描線] 11355 - Cool Points＠Morris' Blog

2014-03-04 08:03:01| 人氣1,585| 回應0 | 上一篇 | 下一篇

[UVA][掃描線] 11355 - Cool Points

推薦 0 收藏 0 轉貼0 訂閱站台

C	Next Generation Contest - 4	Time Limit – 2 secs
	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 x₁, y₁, x₂ and y₂. (x₁, y₁) – (x₂, y₂) 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

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 <stdio.h>
#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
*/

我要檢舉

#11355#Cool Points#掃描線

台長： Morris

您可能對以下文章有興趣

[UVA][spfa] 318 - Domino Effect

[UVA][Java] 10669 - Three powers

[UVA][Tree] 12458 - Oh, my trees!

[UVA][dp][Edit distance] 164 - String Computer

人氣(1,585) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][BFS] 11359 - Guards, Imbecile Guards
此分類上一篇:[UVA][DP] 11370 - Moogle

回應(0)