青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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;
}

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            午夜精品亚洲| 久久久久久久久蜜桃| 亚洲国产精品激情在线观看| 久久精品一区二区三区不卡| 含羞草久久爱69一区| 久久综合精品国产一区二区三区| 久久久久在线观看| 亚洲人午夜精品| 一区二区三区国产精品| 国产日韩精品一区二区浪潮av| 欧美在线观看网站| 久热精品视频在线| 一区二区三区不卡视频在线观看 | 欧美日韩精品免费在线观看视频| 一区二区三区视频在线播放| 亚洲一卡久久| 在线成人小视频| 亚洲美女在线国产| 韩日欧美一区二区| 亚洲精品一区二区三区四区高清| 国产精品久久久久免费a∨大胸| 久久精品中文| 欧美日本免费| 老司机成人网| 欧美午夜精品久久久久免费视 | 91久久精品www人人做人人爽| 亚洲人成在线播放| 国产亚洲制服色| 久久久久久久网站| 国内精品模特av私拍在线观看| 一区二区三区|亚洲午夜| 亚洲视频播放| 久久久精品国产免费观看同学| 亚洲国产成人精品女人久久久 | 在线观看欧美亚洲| 狠狠色综合日日| 欧美视频一区在线观看| 久久婷婷色综合| 亚洲精品视频啊美女在线直播| 欧美一级电影久久| 亚洲激情电影在线| 欧美在现视频| 午夜精品视频在线| 欧美日韩成人一区| 免费日韩av| 国产亚洲一级| 亚洲一区国产| 亚洲天堂成人| 麻豆freexxxx性91精品| 久久er精品视频| 欧美色欧美亚洲另类七区| 蜜桃av噜噜一区| 国产真实乱偷精品视频免| 亚洲欧美激情在线视频| 在线亚洲电影| 欧美日韩精品中文字幕| 亚洲国产一区二区精品专区| 亚洲国产精品va在线看黑人 | 亚洲一级一区| 欧美日韩国产天堂| 亚洲精品乱码久久久久| 91久久精品美女| 美女露胸一区二区三区| 欧美成年人在线观看| 极品少妇一区二区三区| 久久久精品一品道一区| 久久综合一区二区三区| 国内揄拍国内精品少妇国语| 欧美综合二区| 免费观看一级特黄欧美大片| 在线精品亚洲| 另类专区欧美制服同性| 亚洲高清毛片| 一区二区三区日韩在线观看 | 亚洲在线视频观看| 午夜欧美理论片| 国产老女人精品毛片久久| 亚洲欧美综合v| 麻豆视频一区二区| 亚洲美女区一区| 国产精品成人va在线观看| 亚洲专区欧美专区| 久久久久在线| 日韩一级免费观看| 欧美视频一区二区| 欧美一区二区三区四区在线观看地址 | 在线视频中文亚洲| 国产精品女主播一区二区三区| 性做久久久久久久久| 欧美成人午夜激情在线| 一区二区精品在线| 国产视频久久网| 欧美/亚洲一区| 亚洲视频在线观看一区| 久久久精品一区| 99re这里只有精品6| 国产欧美日韩视频在线观看| 噜噜噜91成人网| 亚洲一区欧美二区| 欧美激情四色 | 亚洲欧洲在线一区| 国产精品亚洲不卡a| 久久久久成人网| 在线亚洲激情| 欧美成年人视频网站欧美| 亚洲欧美999| 亚洲三级视频| 国产主播一区二区三区四区| 欧美乱人伦中文字幕在线| 午夜精品美女久久久久av福利| 亚洲夫妻自拍| 久久久久国产精品人| 亚洲图色在线| 亚洲人成人77777线观看| 国产视频久久| 国产精品任我爽爆在线播放 | 欧美激情一区二区久久久| 久久国产视频网| 亚洲永久字幕| 99在线精品视频| 亚洲福利视频在线| 开心色5月久久精品| 欧美一区二区大片| 亚洲一区二区在线| 日韩图片一区| 亚洲三级视频| 亚洲国产精品一区二区三区| 国产一区欧美日韩| 国产日韩欧美在线视频观看| 国产精品国产三级国产普通话蜜臀 | 久久综合电影| 久久精品主播| 欧美在线欧美在线| 欧美在线视频免费| 欧美一区二区三区免费观看| 亚洲在线观看视频| 亚洲免费伊人电影在线观看av| 亚洲精品视频免费观看| 亚洲国产一区二区三区在线播 | 亚洲一区二区三区免费视频 | 久久蜜桃精品| 久久久亚洲午夜电影| 久久久久国产一区二区三区| 欧美专区一区二区三区| 欧美一区二区三区在线免费观看 | 久久夜色精品国产欧美乱| 久久九九久精品国产免费直播| 欧美在线不卡视频| 久久久久欧美| 欧美高清视频免费观看| 欧美国产一区二区三区激情无套| 欧美 日韩 国产精品免费观看| 欧美激情一区二区在线| 欧美日韩亚洲网| 国产精品丝袜白浆摸在线| 国产婷婷色综合av蜜臀av| 国产一区亚洲一区| 亚洲高清在线播放| 日韩午夜在线电影| 亚洲视频中文字幕| 亚洲女优在线| 麻豆精品在线播放| 亚洲国产欧美久久| 国产精品99久久不卡二区| 亚洲欧洲99久久| 老司机精品福利视频| 欧美日韩午夜| 韩日视频一区| 一区二区三区 在线观看视| 午夜视频在线观看一区二区三区| 久久国产欧美| 亚洲国产视频直播| 亚洲欧美一区二区在线观看| 久久久久久久网| 欧美日韩国产成人在线91| 国产欧美在线| 亚洲美女精品久久| 欧美一级成年大片在线观看| 欧美电影资源| 亚洲一区三区视频在线观看| 久久天堂成人| 国产精品青草久久| 亚洲理伦电影| 久久久噜噜噜久久人人看| 亚洲美女中文字幕| 久久五月婷婷丁香社区| 国产精品高清网站| 亚洲伦理网站| 老司机久久99久久精品播放免费 | 欧美日韩综合| 亚洲欧洲一级| 久久全国免费视频| 亚洲午夜激情在线| 欧美激情成人在线视频| 男女精品视频| 欧美高清免费| 国产精品网站在线| 欧美日韩国产在线一区| 国产精品sm| 国产一区二区成人久久免费影院|