npsc2010_C幽靈特務報到

葉桔良

幽靈特務報到
執行時間限制: 10 秒
幽靈特務是人類的特種部隊，他們擁有高超的隱形狙擊技術並且可以使用電磁脈衝彈來消除敵人的護盾。但最令人難忘的是他們可以導引戰術性核彈進行大規模攻擊，消滅範圍內所有部隊和建築。在政府設置的幽靈特務學院中，幽靈特務學徒們必須接受各種訓練及測試，以引導他們與生俱來的幽能來增加自己的體能及耐力。
引導核彈在幽靈特務學院中是個相當吃重的考試科目，畢竟將核彈發射到錯誤的地方是個非常嚴重的錯誤並且會造成無法挽回的後果。
學院中引導核彈發射的考試方式如下：

這些作為標靶的建築物非常脆弱，不僅是建築物內部，只要建築物的某一角或某一邊觸及核彈的爆炸半徑，整棟建築物即會當場爆炸。標靶建築的形狀都是矩形，並且建築的牆壁會平行於座標軸。兩棟建築物不會互相交叉或覆蓋。
只要想當幽靈特務就不能在這關被當掉，每個學徒都戰戰兢兢地來參加考試。現在場上的學徒終於選定了投擲核彈的座標並且開始瞄準，身為一個看熱鬧的鄉親，你不禁想為他計算一下，這次會考幾分？
輸入檔說明
第一行有一個整數 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

葉桔良

1. #include <iostream>  
   
2. using namespace std;  
   
3. const int maxn = 100005;  
   
4.    
   
5. struct Square {  
   
6.     double x, y, w, l;  
   
7. } sq[maxn];  
   
8.    
   
9. int main() {  
   
10.     ios_base::sync_with_stdio(0);  
    
11.     cin.tie(0);  
    
12.     int T, N;  
    
13.     cin >> T;  
    
14.     while (T--) {  
    
15.         cin >> N;  
    
16.         for (int i = 0; i < N; i++) {  
    
17.             cin >> sq[i].x >> sq[i].y >> sq[i].w >> sq[i].l;  
    
18.         }  
    
19.         double x, y, r;  
    
20.         cin >> x >> y >> r;  
    
21.         int ans = 0;  
    
22.         for (int i = 0; i < N; i++) {  
    
23.             double x1 = sq[i].x - sq[i].w / 2;  
    
24.             double x2 = sq[i].x + sq[i].w / 2;  
    
25.             double y1 = sq[i].y - sq[i].l / 2;  
    
26.             double y2 = sq[i].y + sq[i].l / 2;  
    
27.                
    
28.             if (x >= x1 && x <= x2 && y >= y1 && y <= y2) {  
    
29.                 //圓心在矩形內  
    
30.                 ans++;  
    
31.                 continue;  
    
32.             }  
    
33.                
    
34.             if (x >= x1 && x <= x2) {  
    
35.                 //檢查矩形的四個邊  
    
36.                 if (y < y1 && y + r >= y1) {  
    
37.                     ans++;  
    
38.                     continue;  
    
39.                 }  
    
40.                 if (y > y2 && y - r <= y2) {  
    
41.                     ans++;  
    
42.                     continue;  
    
43.                 }  
    
44.             }  
    
45.             if (y >= y1 && y <= y2) {  
    
46.                 if (x < x1 && x + r >= x1) {  
    
47.                     ans++;  
    
48.                     continue;  
    
49.                 }  
    
50.                 if (x > x2 && x - r <= x2) {  
    
51.                     ans++;  
    
52.                     continue;  
    
53.                 }  
    
54.             }  
    
55.                
    
56.             //檢查矩形的四個角  
    
57.             double a[4][2] = {{x1, y1}, {x1, y2}, {x2, y1}, {x2, y2}};  
    
58.             for (int j = 0; j < 4; j++) {  
    
59.                 if ((x - a[j][0]) * (x - a[j][0]) + (y - a[j][1]) * (y - a[j][1]) <= r * r) {  
    
60.                     ans++;  
    
61.                     break;  
    
62.                 }  
    
63.             }  
    
64.         }  
    
65.         cout << ans << "\n";  
    
66.     }  
    
67.       
    
68.     return 0;  
    
69. }

複製代碼