ZOJ 1360 Radar Installation

[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;
            }
                }
&n

补充：软件开发 , C++ ,

上一个：C++ 数据结构与算法：冒泡排序及改进算法
下一个：二分堆(binary)