提交地址:https://vjudge.net/problem/UVA-11168
题目:
pdf:https://uva.onlinejudge.org/external/111/11168.pdf
给出n个点,找到一条直线,使所有点在直线的同一侧,且到直线的距离之和的平均值最小
解题思路:
这条直线一定是在这些点的凸包的边上,根据凸包上相邻两个点构成一条直线,利用直线的两点式得到直线的一般式:Ax+By+C=0.
根据点到直线的距离公式:,因为这些点都在直线的同一侧,所有距离公式的符号都是相同的,可以先求出sumx和sumy,最终计算的时候直接乘个系数即可。
统计最小的平均距离
ac代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10007;
const double pi = acos(-1.0);
const double eps = 1e-10;
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
friend bool operator < (Point a, Point b)
{
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
};
typedef Point Vector;
Vector operator - (Vector a, Vector b)//向量减法
{
return Vector(a.x - b.x, a.y - b.y);
}
Vector operator + (Vector a, Vector b)//向量加法
{
return Vector(a.x + b.x, a.y + b.y);
}
int dcmp(double x)//精度三态函数(>0,<0,=0)
{
if (fabs(x) < eps)return 0; //等于
else return x < 0 ? -1 : 1;//小于,大于
}
double Cross(Vector a, Vector b)//外积
{
return a.x * b.y - a.y * b.x;
}
Vector Rotate(Vector a, double rad)//逆时针旋转rad弧度
{
return Vector(a.x*cos(rad) - a.y*sin(rad), a.x*sin(rad) + a.y*cos(rad));
}
struct Line//直线标准式
{
double a,b,c;
};
Line GetLine(Point A,Point B)//由两点式求直线标准方程
{
Line L;
L.a=B.y-A.y;
L.b=A.x-B.x;
L.c=B.x*A.y-A.x*B.y;
return L;
}
int ConvexHull(Point *p, int n, Point* ch)//凸包
{
sort(p, p+n);//先x后y
int m = 0;//ch存最终的凸包顶点,下标从0开始
for(int i = 0; i < n; i++)
{
//m是待确定的
while(m > 1 && dcmp(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 && dcmp(Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) <= 0) m--;//同样的方向
ch[m++] = p[i];
}
if(n>1) m--;//m是凸包上的点数+1,相当于n,ch[m]和ch[0]相同,遍历的时候<m即可
return m;
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
int t, n, Case = 0;
scanf("%d", &t);
Point allp[maxn], ch[maxn];
while(t--)
{
scanf("%d", &n);
double sumx = 0, sumy = 0, ans = LONG_LONG_MAX;
for(int i = 0; i < n; i++)
{
scanf("%lf %lf", &allp[i].x, &allp[i].y);
sumx += allp[i].x;
sumy += allp[i].y;
}
if(n <= 2)
{
printf("Case #%d: 0.000\n", ++Case);
continue;
}
int m = ConvexHull(allp, n, ch);
for(int i = 0; i < m; i++)
{
Line L = GetLine(ch[i], ch[(i+1)%m]);
double up = fabs(sumx*L.a + sumy*L.b + n*L.c);
double down = sqrt(L.a*L.a + L.b*L.b);
ans = min(ans, up/down);
}
printf("Case #%d: %.3lf\n",++Case,ans/(n*1.0));
}
return 0;
}