UVA 11168 - Airport - [凸包基础题]

时间:2023-03-09 23:47:29
UVA 11168 - Airport - [凸包基础题]

题目链接:https://cn.vjudge.net/problem/UVA-11168

题意:

给出平面上的n个点,求一条直线,使得所有的点在该直线的同一侧(可以在该直线上),并且所有点到该直线的距离和最小,输出该距离除以n;

题解:

显然最好能让越多的点在这条直线上就越好,但又要所有点满足在同侧,则显然要选取某条凸包边界所在直线作为ans;

求出凸包后,遍历每条凸包边,求出所有点到这条直线的距离和,找到最小的即可。

AC代码:

#include<bits/stdc++.h>
#define MAX 10005
using namespace std; //--------------------------------------计算几何模板 - st-------------------------------------- const double eps = 1e-; struct Point{
double x,y;
Point(double tx=,double ty=):x(tx),y(ty){}
};
typedef Point Vctor; //向量的加减乘除
Vctor operator + (Vctor A,Vctor B){return Vctor(A.x+B.x,A.y+B.y);}
Vctor operator - (Point A,Point B){return Vctor(A.x-B.x,A.y-B.y);}
Vctor operator * (Vctor A,double p){return Vctor(A.x*p,A.y*p);}
Vctor operator / (Vctor A,double p){return Vctor(A.x/p,A.y/p);}
bool operator < (Point A,Point B){return A.x < B.x || (A.x == B.x && A.y < B.y);} struct Line{
Point p;
Vctor v;
Line(Point p=Point(,),Vctor v=Vctor(,)):p(p),v(v){}
Point point(double t){return p + v*t;} //获得直线上的距离p点t个单位长度的点
};
struct Circle{
Point c;
double r;
Circle(Point tc=Point(,),double tr=):c(tc),r(tr){}
Point point(double a){return Point( c.x + cos(a)*r , c.y + sin(a)*r);}
}; int dcmp(double x)
{
if(fabs(x)<eps) return ;
else return (x<)?(-):();
}
bool operator == (Point A,Point B){return dcmp(A.x-B.x)== && dcmp(A.y-B.y)==;} //向量的点积,长度,夹角
double Dot(Vctor A,Vctor B){return A.x*B.x+A.y*B.y;}
double Length(Vctor A){return sqrt(Dot(A,A));}
double Angle(Vctor A,Vctor B){return acos(Dot(A,B)/Length(A)/Length(B));} //叉积,三角形面积
double Cross(Vctor A,Vctor B){return A.x*B.y-A.y*B.x;}
double TriangleArea(Point A,Point B,Point C){return Cross(B-A,C-A);} //向量的旋转,求向量的单位法线(即左转90度,然后长度归一)
Vctor Rotate(Vctor A,double rad){return Vctor( A.x*cos(rad) - A.y*sin(rad) , A.x*sin(rad) + A.y*cos(rad) );}
Vctor Normal(Vctor A)
{
double L = Length(A);
return Vctor(-A.y/L, A.x/L);
} //直线的交点
Point getLineIntersection(Line L1,Line L2)
{
Vctor u = L1.p-L2.p;
double t = Cross(L2.v,u)/Cross(L1.v,L2.v);
return L1.p + L1.v*t;
} //点到直线的距离
double DistanceToLine(Point P,Line L)
{
return fabs(Cross(P-L.p,L.v))/Length(L.v);
} //点到线段的距离
double DistanceToSegment(Point P,Point A,Point B)
{
if(A==B) return Length(P-A);
Vctor v1 = B-A, v2 = P-A, v3 = P-B;
if (dcmp(Dot(v1,v2)) < ) return Length(v2);
else if (dcmp(Dot(v1,v3)) > ) return Length(v3);
else return fabs(Cross(v1,v2))/Length(v1);
} //点到直线的映射
Point getLineProjection(Point P,Line L)
{
return L.v + L.v*Dot(L.v,P-L.p)/Dot(L.v,L.v);
} //判断线段是否规范相交
bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2)
{
double c1 = Cross(a2 - a1,b1 - a1), c2 = Cross(a2 - a1,b2 - a1),
c3 = Cross(b2 - b1,a1 - b1), c4 = Cross(b2 - b1,a2 - b1);
return dcmp(c1)*dcmp(c2)< && dcmp(c3)*dcmp(c4)<;
} //判断点是否在一条线段上
bool OnSegment(Point P,Point a1,Point a2)
{
return dcmp(Cross(a1 - P,a2 - P))== && dcmp(Dot(a1 - P,a2 - P))<;
} //多边形面积
double PolgonArea(Point *p,int n)
{
double area=;
for(int i=;i<n-;i++) area += Cross( p[i]-p[] , p[i + ]-p[] );
return area/;
} //判断圆与直线是否相交以及求出交点
int getLineCircleIntersection(Line L,Circle C,vector<Point> &sol)
{
double t1,t2;
double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
double e = a*a + c*c , f = *(a*b + c*d), g = b*b + d*d - C.r*C.r;
double delta = f*f - 4.0*e*g;
if(dcmp(delta)<) return ;
else if(dcmp(delta)==)
{
t1 = t2 = -f/(2.0*e);
sol.push_back(L.point(t1));
return ;
}
else
{
t1 = (-f-sqrt(delta))/(2.0*e); sol.push_back(L.point(t1));
t2 = (-f+sqrt(delta))/(2.0*e); sol.push_back(L.point(t2));
return ;
}
} //判断并求出两圆的交点
double angle(Vctor v){return atan2(v.y,v.x);}
int getCircleIntersection(Circle C1,Circle C2,vector<Point> &sol)
{
double d = Length(C1.c - C2.c);
//圆心重合
if(dcmp(d)==)
{
if(dcmp(C1.r-C2.r)==) return -; //两圆重合
else return ; //包含关系
} //圆心不重合
if(dcmp(C1.r+C2.r-d)<) return ; // 相离
if(dcmp(fabs(C1.r-C2.r)-d)>) return ; // 包含 double a = angle(C2.c - C1.c);
double da = acos((C1.r*C1.r + d*d - C2.r*C2.r) / (*C1.r*d));
Point p1 = C1.point(a - da), p2 = C1.point(a + da);
sol.push_back(p1);
if(p1==p2) return ;
sol.push_back(p2);
return ;
} //求点到圆的切线
int getTangents(Point p,Circle C,vector<Line> &sol)
{
Vctor u=C.c-p;
double dis=Length(u);
if(dis<C.r) return ;
else if(dcmp(dis-C.r) == )
{
sol.push_back(Line(p,Rotate(u,M_PI/)));
return ;
}
else
{
double ang=asin(C.r/dis);
sol.push_back(Line(p,Rotate(u,-ang)));
sol.push_back(Line(p,Rotate(u,ang)));
return ;
}
} //求两圆的切线
int getCircleTangents(Circle A,Circle B,Point *a,Point *b)
{
int cnt = ;
if(A.r<B.r){swap(A,B);swap(a,b);}
//圆心距的平方
double d2 = (A.c.x - B.c.x)*(A.c.x - B.c.x) + (A.c.y - B.c.y)*(A.c.y - B.c.y);
double rdiff = A.r - B.r;
double rsum = A.r + B.r;
double base = angle(B.c - A.c);
//重合有无限多条
if(d2 == && dcmp(A.r - B.r) == ) return -;
//内切
if(dcmp(d2-rdiff*rdiff) == )
{
a[cnt] = A.point(base);
b[cnt] = B.point(base);
cnt++;
return ;
}
//有外公切线
double ang = acos((A.r - B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt] = B.point(base + ang); cnt++;
a[cnt] = A.point(base - ang); b[cnt] = B.point(base - ang); cnt++; //一条内切线
if(dcmp(d2-rsum*rsum) == )
{
a[cnt] = A.point(base);
b[cnt] = B.point(M_PI + base);
cnt++;
}//两条内切线
else if(dcmp(d2-rsum*rsum) > )
{
double ang = acos((A.r + B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt] = B.point(base + ang); cnt++;
a[cnt] = A.point(base - ang); b[cnt] = B.point(base - ang); cnt++;
}
return cnt;
} //--------------------------------------计算几何模板 - ed--------------------------------------
Point p[MAX]; bool cmp(Point p1,Point p2)
{
double tmp=Cross(p1-p[],p2-p[]);
if(!dcmp(tmp)) return Length(p1-p[])<Length(p2-p[]);
else return tmp>;
}
vector<Point> graham_scan(int n)
{
vector<Point> ans;
int idx=;
for(int i=;i<n;i++)//选出Y坐标最小的点,若Y坐标相等,选择X坐标小的点
{
if(p[i].y<p[idx].y || (p[i].y == p[idx].y && p[i].x < p[idx].x)) idx=i;
}
swap(p[],p[idx]);
sort(p+,p+n,cmp);
for(int i=;i<=;i++) ans.push_back(p[i]);
int top=;
for(int i=;i<n;i++)
{
while(top> && Cross(p[i]-ans[top-],ans[top]-ans[top-]) >= )
{
ans.pop_back();
top--;
}
ans.push_back(p[i]);
top++;
}
return ans;
} int n;
int main()
{
int t;
scanf("%d",&t);
for(int kase=;kase<=t;kase++)
{
scanf("%d",&n);
for(int i=;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
vector<Point> ans=graham_scan(n);
double mini=0x3f3f3f3f;
for(int i=;i<ans.size();i++)
{
Point& p1 = ans[i];
Point& p2 = (i==ans.size()-)?ans[]:ans[i+];
double dist=;
for(int i=;i<n;i++) dist+=DistanceToLine(p[i],Line(p1,p2-p1));
if(dist<mini) mini=dist;
}
printf("Case #%d: %.3lf\n",kase,mini/(1.0*n));
}
}

PS.为保证跟前面的计算几何模板一致性,就把整个模板都copy了。