[editorial] GCJ 2008 Qualification Round C

  • 하나반
    하나반

    이 문제는 알고리즘 보다는 기하학적인 문제이군요. -_-;
    알고리즘 말고.. 수학공부도 많이 해야 할 것 같습니다.
    원의 넓이 공식도 생각안나고 sin, cos 막 헥갈리고.. 좀 많이 헤맸습니다.
    알고리즘은 무척 단순합니다.
    일단 파리가 라켓에 스치기만 해도 죽으니까 다음을 적용합니다.
    [spoiler="더 보기..."]라켓의 줄의 반지름 += 파리의 반지름.
    테두리의 크기 += 파리의 반지름.
    [/spoiler]
    그러면 확률 계산법은 아래와 같이 됩니다.
    [spoiler="더 보기..."]파리가 라켓에 맞을 확률 = (라켓의 줄과 테두리의 넓이) / (라켓의 전체 넓이)
    = ( (라켓의 전체 넓이) - (구멍의 넓이의 합) ) / (라켓의 전체 넓이)[/spoiler]
    구멍의 넓이를 구하는 방법은 라켓의 중심을 기준으로 x,y축으로 나눈 후 1-4분면을 계산해서 4를 곱하고,
    각각의 넓이는 조건에 따라 3가지 경우가 있습니다.
    [spoiler="더 보기..."]// 구멍의 좌표를 (x1, y1) - (x2, y2) 라 하면
    if ( (x1, y1)까지의 거리 > R) // 구멍은 라켓 바깥에 있음.
    면적 = 0;
    else if ( (x2, y2)까지의 거리 < R) // 구멍은 라켓 안쪽에 있음.
    면적 = (x2 - x1) * (y2 - y1);
    else // 구멍이 라켓에 걸쳐져 있음.
    면적 = 사각형과 원이 만나는 부분까지의 삼각형(or 사다리꼴)의 면적 + 원의 중심에서 시작하는 부채꼴의 면적 - 원의 중심에서 양 점을 가지고 그린 삼각형의 면적
    [/spoiler]
    모든 구멍에 대해서 면적을 합해서 확률을 계산하면 됩니다..
    [spoiler="소스 보기"]~~~ c

    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    double PI;
    #define DIST(x, y) sqrt( (x) * (x) + (y) * (y) )
    void calc(int no)
    {
    double f, R, t, r, g;
    double S;
    double ans = 0;
    double x1, x2, y1, y2, cx1, cx2, cy1, cy2;
    double an1, an2, dan;
    double SH = 0, SS;
    int nx = -1, ny = -1;
    int ns = -1, max_s;
    int cnt = 0;
    cin >> f >> R >> t >> r >> g;
    S = R * R * PI;
    r += f;
    R -= t + f;
    g -= 2 * f;
    if (g <= 0) {
    goto out;
    }
    max_s = (int) ceil( (R + r) / (2 * r + g) );
    for (nx = 1; nx <= max_s; nx++) {
    for (ny = 1; ny <= max_s; ny++) {
    x2 = (2 * r + g) * nx - r;
    y2 = (2 * r + g) * ny - r;
    x1 = x2 - g;
    y1 = y2 - g;
    if (R >= DIST(x2, y2) ) {
    SS = g * g;
    } else if (R > DIST(x1, y1) ) {
    cnt++;
    if (R > DIST(x1, y2) ) {
    cy1 = y2;
    cx1 = sqrt(R * R - y2 * y2);
    if (R > DIST(x2, y1) ) {
    cx2 = x2;
    cy2 = sqrt(R * R - x2 * x2);
    SS = (g * g) - (x2 - cx1) * (y2 - cy2) / 2;
    } else {
    cy2 = y1;
    cx2 = sqrt(R * R - y1 * y1);
    SS = (g * (min(cx1, cx2) - x1) ) + g * fabs(cx2 - cx1) / 2;
    }
    } else {
    cx1 = x1;
    cy1 = sqrt(R * R - x1 * x1);
    if (R > DIST(x2, y1) ) {
    cx2 = x2;
    cy2 = sqrt(R * R - x2 * x2);
    SS = (g * (min(cy1, cy2) - y1) ) + g * fabs(cy2 - cy1) / 2;
    } else {
    cy2 = y1;
    cx2 = sqrt(R * R - y1 * y1);
    SS = (cy1 - y1) * (cx2 - x1) / 2;
    }
    }
    if (cx1 == 0) an1 = 0;
    else an1 = atan(cy1 / cx1);
    if (cx2 == 0) an2 = 0;
    else an2 = atan(cy2 / cx2);
    dan = fabs(an2 - an1);
    SS += R * R * dan / 2 - R * R * sin(dan) / 2;
    } else SS = 0;
    SH += SS;
    }
    }
    out:
    ans = (S - 4 * SH) / S;
    printf("Case #%d: %.6f\n", no, ans);
    return;
    }
    int main()
    {
    int n;
    int i;
    PI = acos(0) * 2;
    cin >> n;
    for (i = 0; i < n; i++) calc(i + 1);
    return 0;
    }

    [/spoiler]
<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/47935">원문보기</a>]</div>

    15년 전
4개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    오 생각보다 코드가 짧게 나오는군요 ㄷㄷ


    15년 전 link
  • dgsquare
    dgsquare

    코드가 깔끔해서 이해가 잘 되었습니다
    삼각형, 사각형, 오각형의 경우를 모두 고려하셨네여 :-)


    15년 전 link
  • Pan
    Pan


    부채꼴을 세로로 갈랐을 때 남은 부분의 넓이 공식입니다. ㅎㅎ
    위의 것을 이용하면 부채꼴을 정사각형으로 clipping 했을 때의 영역을 쉽게 구할 수 있습니다.


    15년 전 link
  • 김우현
    김우현

    우왕! 굿이세요!
    이런 방식이 있었네요!


    15년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.