DS实验题 Missile-白红宇

DS实验题 Missile

阅读量：7103 次

发布时间：2019-06-28

本文共 1807 字，大约阅读时间需要 6 分钟。

题目：

提示：并没有精度问题。

原题

思路

设源点为A(x1, y1)和B(x2, y2)。

第一步，用结构体存节点，包括以下元素：

1.横坐标x

2.纵坐标y

3.节点和A的距离平方len1：len1 = (x-x1) * (x-x1) + (y-y1) * (y-y1)

4.节点和B的距离平方len2：len2 = (x-x2) * (x-x2) + (y-y2) * (y-y2)

其中3和4在输入的时候计算。

第二步，假设所有的点都在源点A的圆圈范围：根据与A点的距离平方len1的大小排序，使用sort，写个cmp。

第三步，从排好序的节点n(nodes[n])开始，遍历至nodes[1]，进行以下工作：

(1)假设当前的节点nodes[i]加入源点B的圆圈，逐点维护圆圈B的半径平方的大小(若nodes[i].len2比r大，更新r)：r(r初始化为0)。

(2)判断nodes[i]+r与先前的答案ans是否更小，是的话更新ans。

第三步结束之后即得到最优的答案。

代码

////  main.cpp//  Missile_re////  Created by wasdns on 16/11/23.//  Copyright © 2016年 wasdns. All rights reserved.//#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define maxn 1000000000;using namespace std;struct p{    int x, y;    int len1;    int len2;};p nodes[100005];bool cmp(p p1, p p2){    if (p1.len1 != p2.len1) {        return p1.len1 < p2.len1;    }        return false;}int _max(int a, int b){    if (a > b) {        return a;    }    else return b;}int _min(int a, int b){    if (a < b) {        return a;    }    else return b;}int main(){    int x1, x2, y1, y2;    cin >> x1 >> y1 >> x2 >> y2;        int n, i;    cin >> n;        for (i = 1; i <= n; i++)    {        cin >> nodes[i].x >> nodes[i].y;                nodes[i].len1 = (nodes[i].x - x1) * (nodes[i].x - x1)        + (nodes[i].y - y1) * (nodes[i].y - y1);                nodes[i].len2 = (nodes[i].x - x2) * (nodes[i].x - x2)        + (nodes[i].y - y2) * (nodes[i].y - y2);    }        sort(nodes+1, nodes+n+1, cmp);        int ans = maxn;    int rlen = 0;        for (i = n; i >= 1; i--)    {        rlen = _max(rlen, nodes[i+1].len2);                ans = _min(ans, rlen + nodes[i].len1);    }        cout << ans << endl;        return 0;}/* 0 0 6 0 5 -4 -2 -2 3 4 0 6 -2 9 1 */