程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 1360 Radar Installation

ZOJ 1360 Radar Installation

編輯:C++入門知識

[cpp]
#include <iostream>  
#include <stdio.h>  
#include <algorithm>  
#include <vector>  
#include <cmath>  
using namespace std; 
struct Node { 
        int x, y; 
        double xx; 
}; 
bool cmp(Node a, Node b) { 
        return (a.x > b.x); 

double distant(double x1, double y1, double x2, double y2) { 
        return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)); 

int work(int n, int d) { 
        vector<Node> site; 
        Node tmp; 
        for (int i=0; i<n; i++) { 
                scanf("%d %d", &tmp.x, &tmp.y); 
                if (tmp.y > d) 
                        return -1; 
        tmp.xx = tmp.x + sqrt(d*d - tmp.y*tmp.y); 
                site.push_back(tmp); 
        } 
        sort(site.begin(), site.end(), cmp); 
        int count = 1; 
        double xx; 
        tmp = site.back(); 
    site.pop_back(); 
        xx = tmp.xx; 
                while (!site.empty()) { 
                    tmp = site.back(); 
                    site.pop_back(); 
                    if (distant(tmp.x, tmp.y, xx, 0) <= d) 
                continue; 
            else if (tmp.xx < xx) 
                xx = tmp.xx; 
            else { 
                count++; 
                xx = tmp.xx; 
            } 
                } 
        return count; 

int main() { 
        int n, d; 
        int i=0; 
        while (scanf(" %d %d", &n, &d) == 2) { 
                if (n==0 && d==0) 
                        break; 
                i++; 
                int result = work(n, d); 
                printf("Case %d: %d\n", i, result); 
        } 
        return 0; 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
struct Node {
        int x, y;
        double xx;
};
bool cmp(Node a, Node b) {
        return (a.x > b.x);
}
double distant(double x1, double y1, double x2, double y2) {
        return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
int work(int n, int d) {
        vector<Node> site;
        Node tmp;
        for (int i=0; i<n; i++) {
                scanf("%d %d", &tmp.x, &tmp.y);
                if (tmp.y > d)
                        return -1;
        tmp.xx = tmp.x + sqrt(d*d - tmp.y*tmp.y);
                site.push_back(tmp);
        }
        sort(site.begin(), site.end(), cmp);
        int count = 1;
        double xx;
        tmp = site.back();
    site.pop_back();
        xx = tmp.xx;
                while (!site.empty()) {
                    tmp = site.back();
                    site.pop_back();
                    if (distant(tmp.x, tmp.y, xx, 0) <= d)
                continue;
            else if (tmp.xx < xx)
                xx = tmp.xx;
            else {
                count++;
                xx = tmp.xx;
            }
                }
        return count;
}
int main() {
        int n, d;
        int i=0;
        while (scanf(" %d %d", &n, &d) == 2) {
                if (n==0 && d==0)
                        break;
                i++;
                int result = work(n, d);
                printf("Case %d: %d\n", i, result);
        }
        return 0;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved