• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            oyjpArt ACM/ICPC算法程序設計空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            PKU 1328 Radar Installation

            Posted on 2007-06-22 20:00 oyjpart 閱讀(2997) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽

            Radar Installation
            Time Limit:1000MS  Memory Limit:10000K
            Total Submit:2704 Accepted:564

            Description
            Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.

            We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.


            Figure A Sample Input of Radar Installations



             

            Input
            The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.

            The input is terminated by a line containing pair of zeros

            Output
            For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.

            Sample Input

            3 2
            1 2
            -3 1
            2 1
            1 2
            0 2
            0 0
            

             

            Sample Output

            Case 1: 2
            Case 2: 1
            

             

            Source
            Beijing 2002


            Algorithm: Greedy
            Step 1: 輸入數據 如果有一個點的y坐標大于d 直接輸出-1 長生相應的區間(在某一個區間里任意放置一個Radar 則是這個Island可視)
            Step 2: 按照左端點排序(如果左端點相等 則必須按右邊反向排序, 理由在于下一步為了篩選出包含的 必須的把大范圍的放到前面) 注意這里面最好要用浮點判斷規則
            Step 3: 利用Stack對這些區間做預處理 把被包含的區間標識出來
            Step 4: 貪心選擇右端的點

            #include <stdio.h>
            #include <string.h>
            #include <algorithm>
            #include <math.h>
            using namespace std;

            const int N = 1000;
            const double EPS = 1e-7;

            struct E { double a, b; } e[N];
            int n, d;
            bool ava[N];
            double p[N];

            inline int dblcmp(double a, double b) {
             if( fabs(a-b) < EPS ) return 0;
             if( a-b > 0 ) return 1;
             return -1;
            }

            bool operator<(const E& a, const E& b) {
             if(dblcmp(a.a, b.a) == 0)
              return dblcmp(a.b, b.b) == 1;
             return dblcmp(a.a, b.a) == -1;
            }


            int main() {
             int i, j, x, y;
             int tc = 0;
             while(scanf("%d %d", &n, &d), n + d) {
              tc++;
              int ok = 1;
              for(i = 0; i < n; ++i) {
               scanf("%d %d", &x, &y);
               if(y > d) ok = 0;
               double offset = sqrt ( d * d - y * y );
               e[i].a = x - offset, e[i].b = x + offset;
               ava[i] = 1;
              }
              if(!ok) { printf("Case %d: -1\n", tc); continue; }
              sort(e, e + n);
              int stack[N], top = 0;
              stack[top++] = 0;
              for(i = 1; i < n; ++i) {
               while(top > 0 && dblcmp(e[stack[top-1]].b, e[i].b) != -1)  {
                ava[stack[--top]] = 0;
               }
               stack[top++] = i;
              }
              
              for(i = 0; !ava[i]; ++i);
              p[i] = e[i].b;
              int cnt = 1;
              for(i = i+1; i < n; ++i) if(ava[i]) {
               for(j = i-1; !ava[j]; j--);
               if(p[j] >= e[i].a)  p[i] = p[j];
               else { p[i] = e[i].b; cnt++; }
              }
              printf("Case %d: %d\n", tc, cnt);
             }
             return 0;
            }

            久久精品中文闷骚内射| 久久中文字幕视频、最近更新| 久久久久一本毛久久久| 久久福利青草精品资源站| 国産精品久久久久久久| 久久久亚洲欧洲日产国码是AV| 亚洲国产欧洲综合997久久| 99久久伊人精品综合观看| 97精品伊人久久大香线蕉| AV狠狠色丁香婷婷综合久久| 伊人久久大香线蕉无码麻豆 | 久久精品国产亚洲av水果派| 国产亚洲欧美成人久久片| 久久99精品国产麻豆婷婷| 伊人久久综合成人网| 久久久久久国产精品无码下载| 久久99中文字幕久久| 人妻无码αv中文字幕久久琪琪布| 97久久久精品综合88久久| 久久亚洲精品无码aⅴ大香 | 久久综合精品国产一区二区三区 | 国产产无码乱码精品久久鸭| 香蕉aa三级久久毛片| 蜜臀久久99精品久久久久久 | 久久精品国产72国产精福利| 亚洲精品无码成人片久久| 色综合久久久久网| 亚洲国产成人久久精品影视| 国产精品久久国产精麻豆99网站 | 国产成人精品久久亚洲高清不卡| 狠狠色丁香久久婷婷综合图片| 精品久久久久久99人妻| 热re99久久精品国产99热| 国产精品久久久久久福利漫画| 日韩久久久久久中文人妻| 国产精品18久久久久久vr| 久久久亚洲裙底偷窥综合| 中文字幕久久久久人妻| 亚洲国产精品成人久久| 久久精品国产亚洲av麻豆色欲| 久久av无码专区亚洲av桃花岛|