uva11168

题意

给出一些点坐标，选定一条直线，所有点在直线一侧（或直线上），使得所有点到直线的距离平均值最小。

分析

显然直线一定会经过某两点（或一点），又要求点在直线某一侧，可以直接求出凸包，枚举每条边作为直线。

现在就要快速求出所有点到直线的距离，有求点到直线距离方程 \(\frac{|Ax_0 + By_0 + C|}{\sqrt{A^2+B^2}}\)，注意所有点都在直线同一侧，所有 \(Ax_0 + By_0 + C\) 正负号相同，预处理出所有点横、纵坐标之和即可。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const double INF = 1e18;

const int MAXN = 2e4 + 10;

struct Point {

    double x, y;

    Point(double x = 0, double y = 0) : x(x), y(y) {}

    bool operator < (const Point& p1) const {

        if(x == p1.x) return y < p1.y;

        return x < p1.x;

    }

    void read_point() {

        scanf("%lf%lf", &x, &y);

    }

};

double Cross(Point p1, Point p2) {

    return p1.x * p2.y - p1.y * p2.x;

}

Point operator - (Point p1, Point p2) {

    return Point(p1.x - p2.x, p1.y - p2.y);

}

int ConvexHull(Point* p, int n, Point* ch) {

    sort(p, p + n);

    int m = 0;

    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--;

    return m;

}

// (y - y1) / (y2 - y1) = (x - x1) / (x2 - x1)

// 得到直线 p1-p2 : A * x + B * y + C = 0

// 设 f(x, y) = A * x + B * y + C

// 若 f(x, y) < 0 表示点 (x, y) 在直线的左边（此时可把 p1-p2 当作向量）

void getLine(Point p1, Point p2, double& A, double& B, double& C) {

    A = p2.y - p1.y; B = p1.x - p2.x; C = Cross(p2, p1);

}

Point p[MAXN], ch[MAXN];

int main() {

    int kase = 1, T;

    scanf("%d", &T);

    while(T--) {

        int n;

        double X = 0, Y = 0;

        scanf("%d", &n);

        for(int i = 0; i < n; i++) {

            p[i].read_point();

            X += p[i].x;

            Y += p[i].y;

        }

        int m = ConvexHull(p, n, ch);

        double ans = INF;

        for(int i = 0; i < m; i++) {

            double A, B, C;

            getLine(ch[i], ch[(i + 1) % m], A, B, C);

            ans = min(ans, fabs(A * X + B * Y + C * n) / hypot(A, B) / n);

        }

        if(ans == INF) ans = 0;

        printf("Case #%d: %.3f\n", kase++, ans);

    }

    return 0;

}

巴特西

uva11168

uva11168

题意

分析

code

最新文章

热门文章