[ZJ][圓并、圓交、周長] a648. A - Red Areas＠Morris' Blog

2013-03-29 08:21:49| 人氣1,300| 回應1 | 上一篇 | 下一篇

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

技術規格

1.炸彈的數量N是一個整數，且 1 <= N <= 100。
2.第i個炸彈的座標和半徑都是整數，且 -900 <= xi <= 900 、 -900 <= yi <= 900 、 0 < ri <= 20

3.每個炸彈的位置都不同，任兩個炸彈不會有同樣的座標。

輸入說明：

input的第一行有一個正整數表示接下來有幾組測資。每組測資的第一行有一個正整數N，表示這組測資有幾顆炸彈。接下來的N行，每行都有三個由空格分開的整數，x_i , y_i , 和 r_i , ，表示了第i個炸彈的座標和Red Area的半徑。

輸出說明：

請印出兩個數字，由一個空格隔開。第一個數字a是一個實數， 0 < a < 10 。第二個數字是一個非負整數。而封鎖線的總長度為用科學符號表示的a×10^b。注意，a需印出小數後兩位。

範例輸入：

範例輸出：

1.68 1
5.03 1

提示：

Like to bet?

出處：

陳伶志, PTC 2008 TOI2013 練習題 (管理：stanley17112000)

思路:

對每個圓 A[i] 找到另一個圓 A[j] 與它交兩點，
然後得到這兩點在圓 A[i] 的 theta1, theta2 [-pi, pi] 之間，
然後取 (theta1+theta2)/2 判斷是否在 A[j] 圓中，
如果不在拆成兩個區間 [-pi, theta1] [theta2, pi]，否則 [theta1, theta2]
對於一個圓 A[i] 找到 [-pi, pi] 之間沒有被覆蓋的許多區間，
最後加總答案，ans += A[i].r * sigma(↑.length());

考虑上图中的蓝色圆,绿色的圆和蓝色的圆交于 A,B 2个交点 ,我们在逆时针系下考虑，那么可以知道对于蓝色的圆，它对应的某个 角度区间被覆盖了

假设区间为 [A, B], 并且角度是按照圆心到交点的向量的极角来定义 (为了方便，我一般都把角度转化到 [-pi,pi]区间内) 那么可以知道在这种标识情况下，可能存在以下情况

这种区间的跨度如何解决呢?实际上十分简单，只需要把[A,B] 拆成 [-pi, A], [B,pi]即可,也就是所谓的添加虚拟点。

說明取自 http://hi.baidu.com/aekdycoin/item/b8ff6adc73c0e71dd78ed0d6

整體 O(n*n*logn)

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct Cir {
    double x, y, r;
    int scan() {
        return scanf("%lf %lf %lf", &x, &y, &r) == 3;
    }
};
#define eps 1e-8
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(A.r+B.r+eps < disAB || A.r+disAB+eps < B.r || B.r+disAB+eps < A.r) {
        if(disAB < B.r-A.r)
            return 3; //cover all special case
        return -1;
    }
    double 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)
                v[0].x = A.x-vx*A.r/(B.r-A.r);
                v[0].y = A.y-vy*A.r/(B.r-A.r);
                return 3; // cover all special case
            }//((B)A)
        }
        return 1;
    }
    double theta = acos((A.r*A.r+disAB*disAB-B.r*B.r)/2/A.r/disAB);
    double rvx, rvy;
    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 = 0; j < n; j++) {
                if(i == j) continue;
                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(pow(tx-D[j].x,2)+pow(ty-D[j].y, 2) < pow(D[j].r, 2)) {
                    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+eps)
                    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);
        }
        double a = log10(ans), b;
        b = floor(a);
        a = a-b;
        printf("%.2lf %d\n", pow(10, a), (int)b);
    }
    return 0;
}

我要檢舉

#a648#A - Red Areas#圓并#圓交

台長： Morris

您可能對以下文章有興趣

d017. AB Circle

[ZJ][IDA*] d207. 15 - Puzzle

[ZJ] a746 画蛇添足、a799 正值國、a753 一、最大面積

a144. 整數分拆

人氣(1,300) | 回應(1)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][蒙地卡羅模擬法] a648. A - Red Areas
此分類上一篇:[ZJ] a647. 投資專家

回應(1)