[UVA][圓并、圓交、周長] 10969 - Sweet Dream＠Morris' Blog

2013-03-29 08:42:15| 人氣639| 回應0 | 上一篇 | 下一篇

[UVA][圓并、圓交、周長] 10969 - Sweet Dream

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

Problem F

Sweet Dream

Are you ready to have a sweet dream? OK! Close your eyes (Hey! Do NOT! I was kidding! How can you read the problem statement with your eyes closed? Umm! Let me think . . . Yes! There is a good solution to this problem. Simply, hand this paper to your teammate and let him read it aloud for you)!

. . . You are standing in the middle of a room and you have a handful of discs of different sizes. They are heavy. You somehow feel uncomfortable. Calm down and don’t worry! I am going to help you feel comfortable again. Simply choose one of the discs in your hand randomly and drop it on the floor. Yes! You feel a little more comfortable. Choose and drop another! Then another one! . . . And continue this process until your hands are empty. Now, you are as light as a feather and you are ready to fly away . . .

But don’t be so quick! Before flying away, you should solve a problem. Open your eyes and take a look at the floor. You see the discs you’ve just dropped (To the teammate reading this problem aloud: Show the contents of figure 1 to your teammate who is going to open his eyes now).

Adobe Systems

Figure 1. Discs on the floor viewed from the above

You can see that some discs are partially (or totally) covered by other discs. Your job is to compute the total perimeter of parts of the discs that you can see from the above.

Umm! I think you feel a little bit uncomfortable again. Am I right?

The Input

The first line of input contains a single integer which is the number of test cases. Each test case starts with a single integer , the number of discs originally in your hand followed by lines, the th of which containing three floating-point numbers which are , radius of the th disc and the coordinates of the point on the floor on which the disc has fallen. Two floating-point numbers are assumed to be equal if their absolute difference is less than .

The Output

Output for each test case consists of a line containing a floating-point number which is the total perimeter of part of discs that can be seen from above rounded to 3 decimal digits after the fraction point. The number should have exactly 3 digits after the fraction point.

Sample Input

10 0 0

5 0 0

10 0 0

1 0 0

1 1 0

Sample Output

62.832

10.472

Amirkabir University of Technology - Local Contest - Round #2

做法雷同

[ZJ][圓并、圓交、周長] a648. A - Red Areas

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct Cir {
    double x, y, r;
    int scan() {
        return scanf("%lf %lf %lf", &r, &x, &y) == 3;
    }
};
#define eps 1e-6
struct Pt {
    double x, y;
    bool operator<(const Pt other) const {
        if(fabs(x-other.x) < eps)
            return y < other.y;
        return x < other.x;
    }
};
int IntersectCir(Cir A, Cir B, Pt v[]) { // Pt v[] result buffer
    double disAB = sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
    if(fabs(disAB) < eps && fabs(A.r-B.r) < eps) {
        return 3;
    }
    if(A.r+B.r+eps < disAB || A.r+disAB+eps < B.r || B.r+disAB+eps < A.r) {
        if(disAB < B.r-A.r+eps)
            return 3; //cover all special case
        return -1;
    }
    double x, y, vx, vy;
    vx = B.x - A.x;
    vy = B.y - A.y;
    if(fabs(disAB-A.r-B.r) < eps || fabs(A.r-disAB-B.r) < eps ||
       fabs(B.r-A.r-disAB) < eps) {
        if(fabs(disAB-A.r-B.r) < eps) { // (A)(B)
        } else {
            if(A.r < B.r) { //((A)B)
                return 3; // cover all special case
            } else { //((B)A)
            }
        }
        return 1;
    }
    double theta = acos((A.r*A.r+disAB*disAB-B.r*B.r)/2/A.r/disAB);
    double rvx, rvy; //rotate vector
    rvx = vx*cos(theta)-vy*sin(theta);
    rvy = vx*sin(theta)+vy*cos(theta);
    v[0].x = A.x+rvx*A.r/disAB;
    v[0].y = A.y+rvy*A.r/disAB;
    rvx = vx*cos(-theta)-vy*sin(-theta);
    rvy = vx*sin(-theta)+vy*cos(-theta);
    v[1].x = A.x+rvx*A.r/disAB;
    v[1].y = A.y+rvy*A.r/disAB;
    return 2;
}
const double pi = acos(-1);
int main() {
    int t, n;
    int i, j, k;
    scanf("%d", &t);
    Cir D[105];
    while(t--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            D[i].scan();
        double ans = 0, L, R, M, tx, ty;
        int Iidx;
        Pt Interval[205], p[2];
        for(i = 0; i < n; i++) {
            Iidx = 0;
            for(j = i+1; j < n; j++) {
                int r = IntersectCir(D[i], D[j], p);
                if(r == 3) break;
                if(r < 2)   continue;
                L = atan2(p[0].y-D[i].y, p[0].x-D[i].x);
                R = atan2(p[1].y-D[i].y, p[1].x-D[i].x);
                if(L > R)
                    M = L, L = R, R = M;
                M = (L+R)/2;
                tx = D[i].x+D[i].r*cos(M);
                ty = D[i].y+D[i].r*sin(M);
                if((tx-D[j].x)*(tx-D[j].x)+(ty-D[j].y)*(ty-D[j].y) <= D[j].r*D[j].r) {
                    Interval[Iidx].x = L;
                    Interval[Iidx++].y = R;
                } else {
                    Interval[Iidx].x = -pi;
                    Interval[Iidx++].y = L;
                    Interval[Iidx].x = R;
                    Interval[Iidx++].y = pi;
                }
            }
            if(j != n) continue;
            sort(Interval, Interval+Iidx);
            double rr = -pi;
            for(j = 0; j < Iidx; j++) {
                if(Interval[j].x <= rr)
                    rr = max(Interval[j].y, rr);
                else {
                    ans += D[i].r*(Interval[j].x-rr);
                    rr = Interval[j].y;
                }
            }
            ans += D[i].r*(pi-rr);
        }
        printf("%.3lf\n", ans);
    }
    return 0;
}

我要檢舉

#10969#Sweet Dream#圓形交點#圓并#圓交

台長： Morris

您可能對以下文章有興趣

[UVA][二分貪婪] 12255 - Underwater Snipers

[UVA] 750 - 8 Queens Chess Problem

[UVA] 412 - Pi

[UVA][二分greedy] 11920 - 0 s, 1 s and ? Marks

人氣(639) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][bitmask暴搜] 565 - Pizza Anyone?
此分類上一篇:[UVA][幾何、圓交] 453 - Intersecting Circles

回應(0)