Codeforces Round #340 (Div. 2) C. Watering Flowers 计算几何、圆和点

Source

Codeforces Round #340 (Div. 2)

My Solution

O(n)的预处理出所有点到到那个圆心的距离，val[i].r1 val[i].r2;

然后 对于每个val[i]. r1 扫一遍 val[j]， 当 val[j].r1 > r1 的时候 更新 r2 = max(r2, val[j].r2); 就像这个图

然后对应每个i， 更新一次ans， ans = min(ans, r1 + r2);

然后就是可能会都是只用到一个圆心，所以在放一个点 val[n].r1 = 0; val[n].r2 =  0)进去(val[n])， 

所以从 0 到 n 考虑 n + 1个点， 如果取到了 r1 == 0, 则只用到 圆心 2， 同理 用到 r2 == 0, 则只用到圆 1

复杂度 O(n ^ 2)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 2*1e3 + 8;

struct p{
    LL r1, r2;//x, y, mindist, ;
    /*
    bool operator < (const p &b) const { return ((this->mindist) < b.mindist); } */ }val[maxn]; inline LL pow2(LL x) { return x * x; } int main() { #ifdef LOCAL freopen("c.txt", "r", stdin); //freopen("o.txt", "w", stdout); int T = 3; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); LL n, x1, y1, x2, y2, r1, r2, x, y, ans = 1e18; cin >> n;
    cin >> x1 >> y1 >> x2 >> y2;
    for(int i = 0; i < n; i++){ cin >> x >> y;
        val[i].r1 = pow2(x - x1) + pow2(y - y1);
        val[i].r2 = pow2(x - x2) + pow2(y - y2);
    }

    for(int i = 0; i <= n; i++){
        r1 = val[i].r1;
        r2 = 0;
        for(int j = 0; j <= n; j++){ if(val[j].r1 > r1){
                r2 = max(r2, val[j].r2);
            }
        }
        ans = min(ans, r1 + r2);
    }


    cout << ans << endl;                                //n == 1 时比较特殊
    //if(n != 1)cout << ans << endl;
    //else cout << min(val[0].r1, val[0].r2) << endl;


    #ifdef LOCAL
    cout<<endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx