d931. C. 幽靈特務報到＠Morris' Blog｜PChome Online 個人新聞台

2011-06-14 21:07:21| 人氣2,143| 回應2 | 上一篇 | 下一篇

d931. C. 幽靈特務報到

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

http://zerojudge.tw/ShowProblem?problemid=d931

內容：

　　幽靈特務是人類的特種部隊，他們擁有高超的隱形狙擊技術並且可以使用電磁脈衝彈來消除敵人的護盾。但最令人難忘的是他們可以導引戰術性核彈進行大規模攻擊，消滅範圍內所有部隊和建築。在政府設置的幽靈特務學院中，幽靈特務學徒們必須接受各種訓練及測試，以引導他們與生俱來的幽能來增加自己的體能及耐力。

　　引導核彈在幽靈特務學院中是個相當吃重的考試科目，畢竟將核彈發射到錯誤的地方是個非常嚴重的錯誤並且會造成無法挽回的後果。

學院中引導核彈發射的考試方式如下：

【目標】

使用一顆戰術性核彈摧毀最多的標靶建築物，每摧毀一棟建築物可以得一分。

　　這些作為標靶的建築物非常脆弱，不僅是建築物內部，只要建築物的某一角或某一邊觸及核彈的爆炸半徑，整棟建築物即會當場爆炸。標靶建築的形狀都是矩形，並且建築的牆壁會平行於座標軸。兩棟建築物不會互相交叉或覆蓋。

　　只要想當幽靈特務就不能在這關被當掉，每個學徒都戰戰兢兢地來參加考試。現在場上的學徒終於選定了投擲核彈的座標並且開始瞄準，身為一個看熱鬧的鄉親，你不禁想為他計算一下，這次會考幾分？

輸入說明：

第一行有一個整數 T，代表總共有多少筆測試資料。

　　每筆測試資料的第一行包含一個數字 1 ≤ N ≤ 100000，表示有幾棟標靶建築。接下來 N 行內容為：

xi yi widthi lengthi

　　其中 (xi, yi) 這棟建築的中心座標，而 widthi 和 lengthi 是這棟建築的寬度 (x方向) 和長度 (y方向)。最後一行包含一個座標 (x, y)，代表場上學徒瞄準的座標，以及一個浮點數 r 代表核彈爆炸的半徑。所有座標以及建築的長寬均以浮點數表示，並且以上數字取絕對值以後都會小於 100。

輸出說明：

對每組測試資料輸出一個數字，代表這次的考試能得到幾分。

範例輸入：

2
3
0.0 0.0 1.0 1.0
0.0 3.0 1.0 1.0
3.0 0.0 1.0 1.0
1.0 1.0 1.0
3
0.0 0.0 1.0 1.0
0.0 3.0 1.0 1.0
3.0 0.0 1.0 1.0
1.0 1.0 2.0

範例輸出：

1
3

提示：

出處：

2010 NPSC 國中組初賽 (管理：pcshic)

作法 : 窮舉所有可能

分成 4 點在外面，邊卻割圓
還有 4 個頂點，在圓內
/**********************************************************************************/
/* Problem: d931 "C. 幽靈特務報到" from 2010 NPSC 國中組初賽          */
/* Language: C                                                                   */
/* Result: AC (1140ms, 3404KB) on ZeroJudge                                      */
/* Author: morris1028 at 2011-06-12 10:46:57                                     */
/**********************************************************************************/

#include<stdio.h>
struct coordinate {
   double x, y, w, l;
}A[100001];
double x, y, r;
double tw, tl, rx, lx, uy, dy;
int T, n, a;
int judgein(double x, double y, double rx, double ry, double r) {
   if((rx-x)*(rx-x) + (ry-y)*(ry-y) <= r*r) return 1;
   return 0;
}
double point() {
   char cha;
   double poi = 0, num = 1;
    while(cha = getchar())   {
       if(cha == ' ' || cha == '\n') break;
       num=num/10;
       poi=poi + (cha-48)*num;
   }
   return poi;
}
double Input() {
    char cha,flag = 1;
    double x = 0;
   while(cha = getchar())
       if(cha != ' ' && cha != '\n') break;
    if(cha != '-') x = x*10 + cha-48;
    else flag = -1;
    while(cha = getchar()) {
       if(cha == ' ' || cha == '\n') break;
       if(cha == '.') {
           x = x + point();
            break;
        }
        x = x*10 + cha-48;
   }
    return x*flag;
}
main() {

   scanf("%d", &T);
   while(T--) {
       scanf("%d", &n);
       for(a = 0; a < n; a++) {
           A[a].x = Input(), A[a].y = Input(), A[a].w = Input(), A[a].l = Input();
       }
       scanf("%lf %lf %lf", &x, &y, &r);
       int Ans = 0;
       for(a = 0; a < n; a++) {

           if(A[a].x + A[a].w/2 >= x - r && A[a].x - A[a].w/2 <= x + r
           && A[a].y + A[a].l/2 >= y && A[a].y - A[a].l/2 <= y) Ans++;
           else if(A[a].x + A[a].w/2 >= x && A[a].x - A[a].w/2 <= x
           && A[a].y + A[a].l/2 + r >= y && A[a].y - A[a].l/2 - r <= y) Ans++;
           else {
               tw = A[a].w /2.0, tl = A[a].l /2.0;
               rx = A[a].x + tw, lx = A[a].x - tw;
               uy = A[a].y + tl, dy = A[a].y - tl;
               if(judgein(rx, uy, x, y, r)) Ans++;
               else if(judgein(rx, dy, x, y, r)) Ans++;
               else if(judgein(lx, uy, x, y, r)) Ans++;
               else if(judgein(lx, dy, x, y, r)) Ans++;
           }
       }
       printf("%d\n", Ans);
   }
   return 0;
}

我要檢舉

#d931#C. 幽靈特務報到

台長： Morris

您可能對以下文章有興趣

b207. F. 世界盃

b046. E. 智慧型單字查詢

d589. B. 水之國的奇幻冒險

[ZJ][KM算法] d210. 老問題

人氣(2,143) | 回應(2)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: NPSC |
此分類下一篇:b255. D. 跑跑卡丁車
此分類上一篇:d930. B. 薑餅部落的危機

回應(2)