微软2014编程之美初赛第一场——题目3 : 活动中心

【来源】

题目3 : 活动中心

【分析】

本题採用的是三分法。

输入的一组点中找出左右边界。作为起始边界。
while(右边界-左边界<精度){
  将左右边界构成的线段均匀分成3段，推断切割点的距离关系，抹去距离大的一段。更新左右边界。
} 
输出左(右)边界

【代码】

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;

struct Point
{
    int x;
    int y;
};

double calc(double x, vector<Point> points)
{
    double distance = 0;
    for (int i = 0; i < points.size(); ++i){
        double d = (points[i].x - x)*(points[i].x - x) + (points[i].y)*(points[i].y);
        distance += sqrt(d);
    }

    return distance;
}

int main()
{
    int T;
    cin >> T;
    for(int casenum = 0; casenum < T; ++casenum){
        int N;
        cin >> N;
        vector<Point> points;
        Point p;
        double maxX = -1000000;
        double minX = 1000000;
        for (int i = 0; i < N; ++i){
            cin >> p.x >> p.y;
            if (p.x < minX){
                minX = p.x;
            }
            if (p.x > maxX){
                maxX = p.x;
            }
            points.push_back(p);
        }
        double left = minX;
        double right = maxX;
        double m1, m2;

        while (right - left >= 5e-8){
            m1 = (left * 2 + right) / 3.0;
            m2 = (right * 2 + left) / 3.0;
            double v1 = calc(m1, points);
            double v2 = calc(m2, points);
            if (v1 < v2){
                right = m2;
            }
            else{
                left = m1;
            }
        }

        cout << fixed << setprecision(8);
        cout << "Case " << casenum+1 << ": " << left << endl;
    }

    //system("pause");

    return 0;
}

【点评】

本题与去年编程之美的题目集会很相似。

解法也比較雷同。

【备注】

本代码小数据AC，大数据WA。