http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=533&page=show_problem&problem=2109

  1. 选择在凸包上的直线更好
  2. 如何算距离?观察到(对于某一条直线,由于所有点都在直线一侧,所以所有的符号相同),所以预处理后可以求之。
/*0.049s*/

#include<bits/stdc++.h>
using namespace std;

struct Point
{
    double x, y;
    Point(double x = 0, double y = 0): x(x), y(y) {}
};
typedef Point Vector;

Vector operator - (const Point& A, const Point& B)
{
    return Vector(A.x - B.x, A.y - B.y);
}

double Cross(const Vector& A, const Vector& B)
{
    return A.x * B.y - A.y * B.x;
}

bool operator < (const Point& p1, const Point& p2)
{
    return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}

bool operator == (const Point& p1, const Point& p2)
{
    return p1.x == p2.x && p1.y == p2.y;
}

/// 点集凸包
/// 如果不希望在凸包的边上有输入点,把两个 <= 改成 <
/// 如果不介意点集被修改,可以改成传递引用
vector<Point> ConvexHull(vector<Point> p)
{
    /// 预处理,删除重复点
 sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size();
    int m = 0;
    vector<Point> ch(n + 1);
    for (int i = 0; i < n; i++)
    {
        while (m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m--;
        ch[m++] = p[i];
    }
    int k = m;
    for (int i = n - 2; i >= 0; i--)
    {
        while (m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m--;
        ch[m++] = p[i];
    }
    if (n > 1) m--;
    ch.resize(m);
    return ch;
}

/// 过两点p1, p2的直线一般方程ax+by+c=0
/// (x2-x1)(y-y1) = (y2-y1)(x-x1)
void getLineGeneralEquation(const Point& p1, const Point& p2, double& a, double& b, double &c)
{
    a = p2.y - p1.y;
    b = p1.x - p2.x;
    c = -a * p1.x - b * p1.y;
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int kase = 1; kase <= T; kase++)
    {
        int n;
        scanf("%d", &n);
        vector<Point> P;
        double sumx = 0, sumy = 0;
        for (int i = 0; i < n; i++)
        {
            double x, y;
            scanf("%lf%lf", &x, &y);
            sumx += x;
            sumy += y;
            P.push_back(Point(x, y));
        }
        vector<Point> ch = ConvexHull(P);
        int m = ch.size();
        double ans = 1e9;
        if (m <= 2) ans = 0; /// 凸包退化成点或线段,则答案为0
     else for (int i = 0; i < ch.size(); i++)
            {
                double a, b, c;
                getLineGeneralEquation(ch[i], ch[(i + 1) % ch.size()], a, b, c);
                ans = min(ans, fabs(a * sumx + b * sumy + c * n) / sqrt(a * a + b * b));
            }
        printf("Case #%d: %.3f\n", kase, ans / n);
    }
    return 0;
}

Comments

comments powered by Disqus