常用.txt

normal template for acm/ICPC

    c.y = Sqrt( len2 * len2 - c.x * c.x ) ;
    TRIANGLE temp(a,b,c);
    return temp;
};

//三角形费马点(即三角形到三顶点之和最小的点)
POINT fermentPONT(TRIANGLE & t) 
{
    POINT u,v;
    double step=fabs(t.a.x)+fabs(t.a.y)+fabs(t.b.x)+fabs(t.b.y)+fabs(t.c.x)+fabs(t.c.y);
    int i,j,k;
    u.x=(t.a.x+t.b.x+t.c.x)/3;
    u.y=(t.a.y+t.b.y+t.c.y)/3;
    while (step>1e-10)
    for(k=0;k<10;step/=2,k++)
    for(i=-1;i<=1;i++)
    for(j=-1;j<=1;j++)
    {
        v.x=u.x+step*i;
        v.y=u.y+step*j;
        if(Distance(u,t.a)+Distance(u,t.b)+Distance(u,t.c)>Distance(v,t.a)+Distance(v,t.b)+Distance(v,t.c))
        u=v;
    }
    return u;
};

//三角形重心(中线交点)   
POINT InCenter(const TRIANGLE & t)   
{   
  return POINT((t.a.x+t.b.x+t.c.x)/3,(t.a.y+t.b.y+t.c.y)/3);   
}  
 
//三角形外心(中垂线交点)   
POINT CcCenter(const TRIANGLE & t)   
{   
  POINT u,v;   
  LINE A,B;   
  A.a=t.a;A.b=t.b;B.a=t.b;B.b=t.c;   
  TYPE A1, B1, C1;   
  TYPE A2, B2, C2;   
  Coefficient(A, B1, A1, C1);   
  Coefficient(B, B2, A2, C2);   
  B1=-B1;B2=-B2;   
  C1=-( (A.a.x+A.b.x)*A1 + (A.a.y+B.a.y)*B1 ) / 2;   
  C2=-( (B.a.x+B.b.x)*A2 + (B.a.y+B.b.y)*B2 ) / 2;   
  POINT I(0, 0);   
  I.x = - (B2 * C1 - B1 * C2) / (A1 * B2 - A2 * B1);   
  I.y =   (A2 * C1 - A1 * C2) / (A1 * B2 - A2 * B1);   
  return I;   
} 

//三角形内心(角平分线交点) 
POINT incenter(const TRIANGLE & t) 
{
    LINE u,v;
    TYPE m,n;
    u.a=t.a;
    m=atan2(t.b.y-t.a.y,t.b.x-t.a.x);
    n=atan2(t.c.y-t.a.y,t.c.x-t.a.x);
    u.b.x=u.a.x+cos((m+n)/2);
    u.b.y=u.a.y+sin((m+n)/2);
    v.a=t.b;
    m=atan2(t.a.y-t.b.y,t.a.x-t.b.x);
    n=atan2(t.c.y-t.b.y,t.c.x-t.b.x);
    v.b.x=v.a.x+cos((m+n)/2);
    v.b.y=v.a.y+sin((m+n)/2);
    return Intersection(u,v);
};

//三角形内切圆面积
TYPE InArea(const TRIANGLE & t) 
{
  TYPE p,a,b,c,s;
  a=Distance(t.a,t.b);
  c=Distance(t.a,t.c);
  b=Distance(t.c,t.b);
  s=(a+b+c)/2;
  p=s * (s - a) * (s - b) * (s - c); 
  s=p*PI/s/s;
  return s;
}

//三角形外接圆面积
TYPE OutArea(const TRIANGLE & t) 
{
  TYPE a,b,c;
  a=(t.a.x-t.b.x)*(t.a.x-t.b.x)+(t.a.y-t.b.y)*(t.a.y-t.b.y); 
  b=(t.a.x-t.c.x)*(t.a.x-t.c.x)+(t.a.y-t.c.y)*(t.a.y-t.c.y); 
  c=(t.c.x-t.b.x)*(t.c.x-t.b.x)+(t.c.y-t.b.y)*(t.c.y-t.b.y); 
  a=PI*sqrt(c/(1-(a+b-c)*(a+b-c)/a/b/4)); 
  return a; 
} 

// 多边形 ,逆时针或顺时针给出x,y     
struct POLY   
{   
  int n;     //n个点     
  TYPE * x;   //x,y为点的指针，首尾必须重合     
  TYPE * y;   
  POLY() : n(0), x(NULL), y(NULL) {};   
  POLY(int _n_, const TYPE * _x_, const TYPE * _y_)   
  {       
    n = _n_;   
    x = new TYPE[n + 1];   
    memcpy(x, _x_, n*sizeof(TYPE));   
    x[n] = _x_[0];   
    y = new TYPE[n + 1];   
    memcpy(y, _y_, n*sizeof(TYPE));   
    y[n] = _y_[0];   
  }   
}; 
  
//多边形顶点     
POINT Vertex(const POLY & poly, int idx)   
{   
  // idx %= poly.n;   
  return POINT(poly.x[idx], poly.y[idx]);   
}   

//多边形的边     
SEG Edge(const POLY & poly, int idx)   
{   
  // idx %= poly.n;   
  return SEG(POINT(poly.x[idx], poly.y[idx]),     
    POINT(poly.x[idx + 1], poly.y[idx + 1]));   
}  
 
//多边形的周长     
TYPE Perimeter(const POLY & poly)   
{   
  TYPE p = 0.0;   
  for (int i = 0; i < poly.n; i++)   
    p += Distance(Vertex(poly, i), Vertex(poly, i + 1));   
  return p;   
}   

//求多边形面积     
TYPE Area(const POLY & poly)   
{   
  if (poly.n < 3) return TYPE(0);   
  double s = poly.y[0] * (poly.x[poly.n - 1] - poly.x[1]);   
  for (int i = 1; i < poly.n; i++)   
  {   
    s += poly.y[i] * (poly.x[i - 1] - poly.x[(i + 1) % poly.n]);   
  }   
  return s/2;   
}   

//多边形的重心 
POINT InCenter(const POLY & poly)   
{ 
  TYPE S,Si,Ax,Ay; 
  POINT p; 
  Si = (poly.x[poly.n - 1] * poly.y[0] - poly.x[0] * poly.y[poly.n - 1]); 
  S = Si; 
  Ax = Si * (poly.x[0] + poly.x[poly.n - 1]); 
  Ay = Si * (poly.y[0] + poly.y[poly.n - 1]);           
  for(int i=1;i<poly.n;i++){   
    Si=(poly.x[i-1] * poly.y[i] - poly.x[i] * poly.y[i-1]); 
    Ax += Si * ( poly.x[i-1] + poly.x[i] ); 
    Ay += Si * ( poly.y[i-1] + poly.y[i] ); 
    S+=Si; 
  } 
  S=S*3; 
  return POINT(Ax/S,Ay/S);   
}   
  
//判断点是否在多边形上     
bool IsOnPoly(const POLY & poly, const POINT & p)   
{   
  for(int i = 0; i < poly.n; i++)   
  {   
    if( IsOnSeg(Edge(poly, i), p) ) return true;
  }   
  return false;   
}   

//判断点是否在多边形内部     
bool IsInPoly(const POLY & poly, const POINT & p)     
{   
  SEG L(p, POINT(Infinity, p.y));   

  int count = 0;   
  for (int i = 0; i < poly.n; i++)   
  {   
    SEG S = Edge(poly, i);   
    if (IsOnSeg(S, p))   
    {   
        return true; //如果想让 在poly上则返回 true,   
    }   
    if(!IsEqual(S.a.y, S.b.y))   
    {   
        POINT & q = (S.a.y > S.b.y)?(S.a):(S.b);   
        if(IsOnSeg(L, q)) ++count;   
        else if(!IsOnSeg(L, S.a) && !IsOnSeg(L, S.b) && IsIntersect(S, L))   
        {   
          ++count;   
        }   
    }   
  }   
  return (count % 2 != 0);   
}   

//判断是否简单多边形     
bool IsSimple(const POLY & poly)   
{   
  if (poly.n < 3)   
    return false;   
  SEG L1, L2;   
  for(int i = 0; i < poly.n - 1; i++)   
  {   
    L1 = Edge(poly, i);   
    for(int j = i + 1; j < poly.n; j++)   
    {   
        L2 = Edge(poly, j);   
        if(j == i + 1)   
            if(IsOnSeg(L1, L2.b) || IsOnSeg(L2, L1.a)) return false;       
        else if(j == poly.n - i - 1)   
        {   
          if (IsOnSeg(L1, L2.a) || IsOnSeg(L2, L1.b)) return false;               
        }   
        else if(IsIntersect(L1, L2)) return false;     
    } // for j   
  } // for i   
  return true;   
}   

// 点阵的凸包，返回一个多边形(求法一，已测试)   
POLY ConvexHull(const POINT * set, int n)         // 不适用于点少于三个的情况   
{   
  POINT * points = new POINT[n];   
  memcpy(points, set, n * sizeof(POINT));   
  TYPE * X = new TYPE[n];   
  TYPE * Y = new TYPE[n];   
  int i, j, k = 0, top = 2;   
  for(i = 1; i < n; i++)   
  {   
    if ((points[i].y < points[k].y) ||   
        ((points[i].y == points[k].y) &&   
        (points[i].x < points[k].x)))   
    {   
        k = i;   
    }   
  }   
  swap(points[0], points[k]);   
  for(i = 1; i < n - 1; i++)   
  {   
    k = i;   
    for(j = i + 1; j < n; j++)   
    {   
        if((Cross(points[j], points[k], points[0]) > 0) ||   
          ((Cross(points[j], points[k], points[0]) == 0) &&   
          (Distance(points[0], points[j]) < Distance(points[0], points[k]))))   
        {   
          k = j;   
        }   
    }   
    std::swap(points[i], points[k]);   
  }   
  X[0] = points[0].x; Y[0] = points[0].y;   
  X[1] = points[1].x; Y[1] = points[1].y;   
  X[2] = points[2].x; Y[2] = points[2].y;   
  for(i = 3; i < n; i++)   
  {   
    while(Cross(points[i], POINT(X[top], Y[top]),POINT(X[top - 1], Y[top - 1])) >= 0)   
    {   
        top--;   
    }   
    ++top;   
    X[top] = points[i].x;   
    Y[top] = points[i].y;   
  }   
  delete [] points;   
  POLY poly(++top, X, Y);   
  delete [] X;   
  delete [] Y;   
  return poly;   
} 
// 点阵的凸包，返回一个多边形 (求法二，未测试) 
bool cmp(const POINT& aa, const POINT& bb)     
{     
  if(aa.y!= bb.y) return aa.y < bb.y;     
  else return aa.x<bb.x;   
} 
POLY ConvexHull2(const POINT * set, int n) // 不适用于点少于三个的情况   
{ 
  POINT * a = new POINT[n];   
  memcpy(a, set, n * sizeof(POINT)); 
  sort(a, a+n, cmp); 
  TYPE * X = new TYPE[n];   
  TYPE * Y = new TYPE[n];   
  X[0]=a[0].x;   
  Y[0]=a[0].y;   
  X[1]=a[1].x;   
  Y[1]=a[1].y;   
  int i,j; 
  for(i=2,j=2;i<n;i++)
  { 
      X[j]=a[i].x; 
      Y[j]=a[i].y; 
      while(((X[j]-X[j-1])*(Y[j-1]-Y[j-2])-(Y[j]-Y[j-1])*(X[j-1]-X[j-2]))>=0&&j>1)
      { 
        X[j-1]=X[j]; 
        Y[j-1]=Y[j]; 
        j--; 
      } 
      j++; 
  }   
  X[j]=a[n-2].x;   
  Y[j]=a[n-2].y;   
  j++;   
  for(i=n-3;i>=0;i--)
  {   
      X[j]=a[i].x; 
      Y[j]=a[i].y; 
      while(((X[j]-X[j-1])*(Y[j-1]-Y[j-2])-(Y[j]-Y[j-1])*(X[j-1]-X[j-2]))>=0)
      { 
          X[j-1]=X[j]; 
          Y[j-1]=Y[j]; 
          j--; 
      } 
      j++; 
  } 
  delete [] a;   
  POLY poly(j, X, Y);   
  delete [] X;   
  delete [] Y;   
  return poly;   
} 
  
int main()   
{   
    double a,b,c,l1,l2,l3,l4;
    POINT d;
    int n;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%lf%lf%lf",&a,&b,&c);
        TRIANGLE t=StdTRIANGLE(a,b,c);

        d=fermentPONT(t);//费马点
        l1=Distance(d,t.a)+Distance(d,t.b)+Distance(d,t.c);

        d=incenter(t);//内心
        l2=Distance(d,t.a)+Distance(d,t.b)+Distance(d,t.c);

        d=InCenter(t);//重心
        l3=Distance(d,t.a)+Distance(d,t.b)+Distance(d,t.c);

        d=CcCenter(t);//外心
        l4=Distance(d,t.a)+Distance(d,t.b)+Distance(d,t.c);

        printf("%.3lf %.3lf %.3lf %.3lf\n",l1,l2,l3,l4);
    }
    return 0;   
}