题意：

给出平面上n个点，找一条直线

使得所有点在直线的同侧（也可以再直线上）

且到直线的距离之和尽可能小

求最小的平均距离

思路：

要求所有点在直线同侧，因此直线不能穿过凸包。不难发现，选择凸包上的边所在的直线是最优的。关键是求所有点到直线的距离，我们可以枚举每一条凸包上的边，把直线用点斜式表示出来，然后通过一般式求出所有点到直线的总距离。

由于所有点在Ax+By+C = 0的同一侧，所有的Ax0+By0+C的正负号相同。这样，我们在一开始输入时预处理所有x坐标与y坐标之和，就可以方便的算出最短距离啦。

 

我就呵呵了  INF=1<<29; WA  改成0x3f3f3f3f  AC

还是0x3f3f3f3f 科学

 

//大白p263#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;const double eps=1e-10;//精度const int INF=0x3f3f3f3f;const double PI=acos(-1.0);int dcmp(double x){//判断double等于0或。。。 if(fabs(x)
              
                Polygon;Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}//向量+向量=向量Vector operator-(Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}//点-点=向量Vector operator*(Vector a,double p){return Vector(a.x*p,a.y*p);}//向量*实数=向量Vector operator/(Vector a,double p){return Vector(a.x/p,a.y/p);}//向量/实数=向量bool operator<( const Point& A,const Point& B ){return dcmp(A.x-B.x)<0||(dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)<0);}bool operator==(const Point&a,const Point&b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}bool operator!=(const Point&a,const Point&b){return a==b?false:true;}struct Segment{ Point a,b; Segment(){} Segment(Point _a,Point _b){a=_a,b=_b;} bool friend operator<(const Segment& p,const Segment& q){return p.a
               
                
                 0) return tempa-tempb; else return tempa-tempb+2*PI;}double torad(double deg){return deg/180*PI;}//角度化为弧度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));}Vector Normal(Vector a){//计算单位法线 double L=Length(a); return Vector(-a.y/L,a.x/L);}Point GetLineProjection(Point p,Point a,Point b){//点在直线上的投影 Vector v=b-a; return a+v*(Dot(v,p-a)/Dot(v,v));}Point GetLineIntersection(Point p,Vector v,Point q,Vector w){//求直线交点 有唯一交点时可用 Vector u=p-q; double t=Cross(w,u)/Cross(v,w); return p+v*t;}int ConvexHull(Point* p,int n,Point* sol){//计算凸包 sort(p,p+n); int m=0; for(int i=0;i
                 
                  1&&Cross(sol[m-1]-sol[m-2],p[i]-sol[m-2])<=0) m--; sol[m++]=p[i]; } int k=m; for(int i=n-2;i>=0;i--){ while(m>k&&Cross(sol[m-1]-sol[m-2],p[i]-sol[m-2])<=0) m--; sol[m++]=p[i]; } if(n>0) m--; return m;}double Heron(double a,double b,double c){//海伦公式 double p=(a+b+c)/2; return sqrt(p*(p-a)*(p-b)*(p-c));}bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){//线段规范相交判定 double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1); double c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1); return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;}double CutConvex(const int n,Point* poly, const Point a,const Point b, vector
                  
                    result[3]){//有向直线a b 切割凸多边形 vector
                   
                     points; Point p; Point p1=a,p2=b; int cur,pre; result[0].clear(); result[1].clear(); result[2].clear(); if(n==0) return 0; double tempcross; tempcross=Cross(p2-p1,poly[0]-p1); if(dcmp(tempcross)==0) pre=cur=2; else if(tempcross>0) pre=cur=0; else pre=cur=1; for(int i=0;i
                    
                     0) cur=0; else cur=1; if(cur==pre){ result[cur].push_back(poly[(i+1)%n]); } else{ p1=poly[i]; p2=poly[(i+1)%n]; p=GetLineIntersection(p1,p2-p1,a,b-a); points.push_back(p); result[pre].push_back(p); result[cur].push_back(p); result[cur].push_back(poly[(i+1)%n]); pre=cur; } } sort(points.begin(),points.end()); if(points.size()<2){ return 0; } else{ return Length(points.front()-points.back()); }}double DistanceToSegment(Point p,Segment s){//点到线段的距离 if(s.a==s.b) return Length(p-s.a); Vector v1=s.b-s.a,v2=p-s.a,v3=p-s.b; if(dcmp(Dot(v1,v2))<0) return Length(v2); else if(dcmp(Dot(v1,v3))>0) return Length(v3); else return fabs(Cross(v1,v2))/Length(v1);}bool isPointOnSegment(Point p,Segment s){ return dcmp(Cross(s.a-p,s.b-p))==0&&dcmp(Dot(s.a-p,s.b-p))<0;}int isPointInPolygon(Point p, Point* poly,int n){//点与多边形的位置关系 int wn=0; for(int i=0;i
                     
                      0&&d1<=0&&d2>0)wn++; if(k<0&&d2<=0&&d1>0)wn--; } if(wn) return 1;//点在内部 else return 0;//点在外部}double PolygonArea(Point* p,int n){//多边形有向面积 double area=0; for(int i=1;i
                      
                       Cross(ch[q]-ch[p+1],ch[p]-ch[p+1])) q=(q+1)%n; ans=max(ans,max(Length(ch[p]-ch[q]),Length(ch[p+1]-ch[q+1]))); } return ans;}Polygon CutPolygon(Polygon poly,Point a,Point b){//用a->b切割多边形 返回左侧 Polygon newpoly; int n=poly.size(); for(int i=0;i
                       
                        =0) newpoly.push_back(c); if(dcmp(Cross(b-a,c-d))!=0){ Point ip=GetLineIntersection(a,b-a,c,d-c); if(isPointOnSegment(ip,Segment(c,d))) newpoly.push_back(ip); } } return newpoly;}int GetCircleCircleIntersection(Circle c1,Circle c2,Point& p1,Point& p2){ double d=Length(c1.c-c2.c); if(dcmp(d)==0){ if(dcmp(c1.r-c2.r)==0) return -1;//两圆重合 return 0; } if(dcmp(c1.r+c2.r-d)<0) return 0; if(dcmp(fabs(c1.r-c2.r)-d)>0) return 0; double a=Angle(c2.c-c1.c,Vector(1,0)); double da=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d)); p1=c1.point(a-da);p2=c1.point(a+da); if(p1==p2) return 1; return 2;}//两点式化为一般式A = b.y-a.y, B = a.x-b.x, C = -a.y*(B)-a.x*(A);//--------------------------------------//--------------------------------------//--------------------------------------//--------------------------------------//--------------------------------------Point P[10010],ch[10010];int main(){ int n,T,cas=1; scanf("%d",&T); while(T--){ scanf("%d",&n); double sumx=0,sumy=0; for(int i=0;i