题意：

给出平面上n个点，找一条直线，使得所有点在直线的同侧，且到直线的距离之平均值尽量小。

先求凸包

易知最优直线一定是凸包的某条边，然后利用点到直线距离公式进行计算。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; struct Point { int x, y; Point(int x=0, int y=0):x(x),y(y) {} }; typedef Point Vector; Vector operator + (const Vector& a, const Vector& b) { return Vector(a.x+b.x, a.y+b.y); } Vector operator - (const Vector& a, const Vector& b) { return Vector(a.x-b.x, a.y-b.y); } Vector operator * (const Vector& a, double p) { return Vector(a.x*p, a.y*p); } Vector operator / (const Vector& a, double p) { return Vector(a.x/p, a.y/p); } bool operator < (const Point& p1, const Point& p2){ return p1.x
        
          ConvexHull(vector
         
           p) { sort(p.begin(), p.end()); p.erase( unique(p.begin(), p.end()), p.end()); int n = p.size(); int m = 0; vector
          
            ch(n+1); for(int i=0; i
           
            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, n, i, j; scanf("%d", &t); for(int cas=1; cas<=t; ++cas) { scanf("%d", &n); int x, y; vector
            
              P; double sumx = 0, sumy = 0; for(i=0; i