poj 1328 我的貪心第一題 爽！！！！！！

Web Board Home Page F.A.Qs Statistical Charts Problems Submit Problem Online Status Prob.ID: Register Update your info Authors ranklist Current Contest Past Contests Scheduled Contests Award Contest lymyfz      Log Out Mail:0(0) Login Log      Archive POJ Challenge Call for Problems Language:Default Radar Installation Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 24639 Accepted: 5296 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 [Submit]   [Go Back]   [Status]   [Discuss] Home Page    Go Back   To top All Rights Reserved 2003-2007 Ying Fuchen,Xu Pengcheng,Xie Di Any problem, Please Contact Administrator #include<iostream> using namespace std; #include<math.h> #include<algorithm> int n,d; struct sign//學會定義了結構體  { double left; double right; }sign1[1005]; double distance1(int left,int right) { if(d*d-right*right<0) return -1; double dis=sqrt((double)d*d-(double)right*right); return dis; } bool comp(sign x,sign y)//學會定義comp  { return x.left<y.left; } int main() { int i,j; int time=0; //int signr,signl; struct  coordinate { int left; int right; }coo[1005]; while(cin>>n>>d,n||d) { int q=0; if(d<=0) q=1; int signcoo[1005]; //     memset(signcoo,0,sizeof(signcoo)); for(i=0;i<n;i++) { cin>>coo[i].left; cin>>coo[i].right; } double temp; int radar=0; int cou=1; for(i=0;i<n;i++) { temp=distance1(coo[i].left,coo[i].right); if(temp<0) q=1; //cout<<temp; //system("pause"); sign1[i].left=(coo[i].left-temp); sign1[i].right=(coo[i].left+temp); } sort(sign1,sign1+n,comp); double right=sign1[0].right; for(i=1;i<n;i++) {                                   //貪心算法  if(sign1[i].left>right) { cou++; right=sign1[i].right; } else if(sign1[i].right<right) right=sign1[i].right; } if(q==1) cou=-1; getchar();//這個回車讓自己輸入，别打出回車  getchar(); //cout<<endl;      cout<<"Case "<<++time<<": "<<cou<<endl; } return 0; }