Language: C++

#include<iostream>
#include<complex>
#include<cmath>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define mp         make_pair

const double eps = 1e-10;

typedef complex<double> P;

class Tri{
public:
  P d[3];
};

pair<P,P> CC_intersection(P a,P b,double r1,double r2){
  double l,m,n;
  double d = abs(a-b);
  double x,y;
  double p,q;
  l=(d*d-r2*r2+r1*r1)/(2*d);
  
  x=a.real()+(b.real()-a.real())*l/d;
  y=a.imag()+(b.imag()-a.imag())*l/d;
  n=sqrt(r1*r1-l*l);
  p=(b.imag()-a.imag())/d*n;
  q=(b.real()-a.real())/d*n;
  return mp(P(x+p,y-q),P(x-p,y+q));
}

int is_intersected_circle(P a,P b,double r1,double r2){
  double d = abs(a-b);
  if (d<eps && abs(r1-r2)<eps)return 3;
  if (d+r2 < r1)return 0;
  if (d+r1 < r2)return 1;
  if (d > r1+r2)return 4;
  return 2;
}

double compute_dist(double x,double y){
  return sqrt(x*x+y*y);
}

double cross(P a,P b){return a.real()*b.imag()-a.imag()*b.real();}

double dot(P a,P b){return a.real()*b.real()+a.imag()*b.imag();}

bool isp(P a,P b,P c){return abs(a-c)+abs(b-c) < abs(a-b)+eps;}

bool is_intersected_ls(P a1,P a2,P b1,P b2){
  if (  ( cross(a2-a1,b1-a1) * cross(a2-a1,b2-a1)<-eps ) && 
	( cross(b2-b1,a1-b1)*cross(b2-b1,a2-b1)<-eps))return true;
  else return false;
}

bool is_in(P* in,P a){
  int cnt =0;
  int n = 3;
  rep(i,n){
    P cur = in[i]-a,next=in[(i+1)%n]-a;
    if (cur.imag() > next.imag())swap(cur,next);
    if (cur.imag()<0 && 0<=next.imag() &&
	cross(next,cur)>=0)cnt++;
    if (isp(in[i],in[(i+1)%n],a))return true;
  }
  if (cnt %2 == 1)return true;
  else return false;
}

double distance_l_p(P a,P b,P c){
  return abs(cross(b-a,c-a))/abs(b-a);
}

P vector_mapping(P a,P b,P c){
  double tmp = distance_l_p(a,b,c);
  double tmp2= abs(c-a);
  double C   = sqrt(tmp2*tmp2-tmp*tmp+eps);
  assert(!(isnan(C)));
  if (dot(b-a,c-a)<0)C*=-1;
  P e = (b-a);
  e/=abs(b-a);
  e*=C;
  return a + e;
}

double dist3d(double x,double y,double z){
  return sqrt(x*x+y*y+z*z);
}

double solve_linear(double A1,double B1,double C1,
		    double A2,double B2,double C2,
		    double x1,double y1,double d1,
		    double x2,double y2,double d2,
		    double x3,double y3,double d3
		    ,Tri *in
		    ){
  if (A1*B2-A2*B1<eps){
    //cout <<"cannot solve"<<endl;
    return -1;
  }
  double y = (A1*C2-A2*C1)/(A1*B2-A2*B1);
  double x = (C1-B1*y)/A1;
  double z = d2*d2 - (x-x2)*(x-x2) - (y-y2)*(y-y2);
  double z1 = d3*d3 - (x-x3)*(x-x3) - (y-y3)*(y-y3);
  double z2 = d1*d1 - (x-x1)*(x-x1) - (y-y1)*(y-y1);
  if (z < 1e-7)return -1;

  return sqrt(z);
  if (isnan(z)||z<0)return -1;
  else return sqrt(z);
}

double ans;
void compute_height(Tri in[4]){
  static P data[3];
  static double r[3];
  REP(i,1,4){
    data[i-1]=vector_mapping(in[i].d[0],in[i].d[1],in[i].d[2]);
    r[i-1]   =  distance_l_p(in[i].d[0],in[i].d[1],in[i].d[2]);
  }
  
  double tmp = solve_linear(2*(data[1].real()-data[0].real()),
			    2*(data[1].imag()-data[0].imag()),
			    r[0]*r[0]-r[1]*r[1]
			    -(data[0].real()*data[0].real()-data[1].real()*data[1].real())
			    -(data[0].imag()*data[0].imag()-data[1].imag()*data[1].imag()),
			    2*(data[1].real()-data[2].real()),
			    2*(data[1].imag()-data[2].imag()),
			    r[2]*r[2]-r[1]*r[1]
			    -(data[2].real()*data[2].real()-data[1].real()*data[1].real())
			    -(data[2].imag()*data[2].imag()-data[1].imag()*data[1].imag()),
			    data[0].real(),data[0].imag(),r[0],
			    data[1].real(),data[1].imag(),r[1],
			    data[2].real(),data[2].imag(),r[2],
			    in
			    );
  if (tmp < 0.00001||isnan(tmp));
  else {
    ans = min(ans,tmp);//,printf("%.8lf\n",tmp);
    return;
  }

  tmp = solve_linear(2*(data[1].real()-data[0].real()),
			    2*(data[1].imag()-data[0].imag()),
			    r[0]*r[0]-r[1]*r[1]
			    -(data[0].real()*data[0].real()-data[1].real()*data[1].real())
			    -(data[0].imag()*data[0].imag()-data[1].imag()*data[1].imag()),
			    2*(data[2].real()-data[1].real()),
			    2*(data[2].imag()-data[1].imag()),
			    r[1]*r[1]-r[2]*r[2]
			    -(data[1].real()*data[1].real()-data[2].real()*data[2].real())
			    -(data[1].imag()*data[1].imag()-data[2].imag()*data[2].imag()),
			    data[0].real(),data[0].imag(),r[0],
			    data[1].real(),data[1].imag(),r[1],
			    data[2].real(),data[2].imag(),r[2],
			    in
			    );
  if (tmp < 0.00001||isnan(tmp));
  else {
    ans = min(ans,tmp);//,printf("%.8lf\n",tmp);
    return;
  }
 
  

  //  if (tmp >20.00000){
  /*      
  if (tmp < 1){
    printf("%.8lf\n",tmp);
    cout << abs(in[1].d[2]-in[2].d[2]) <<" " << 
      abs(in[2].d[2]-in[3].d[2] ) <<" " << abs(in[3].d[2]-in[0].d[2])<<endl;
    rep(i,4){
      cout <<"[";
      rep(j,3){
	cout << in[i].d[j]<<",";
      }
      cout << in[i].d[0] <<"],"<< endl;
    }
    cout << endl;
  }
  */          
}

bool isvalid(Tri in[4]){
  rep(i,4){
    rep(j,3){
      if (in[i].d[j].real()<-100||in[i].d[j].real()>=100 ||
	  in[i].d[j].imag()<-100||in[i].d[j].imag()>=100){
	//		cout <<"invalid " << i <<" coordinate 1"<<endl;
	return false;
      }
      if (in[i].d[j].real()>=0){
	if (abs(floor(in[i].d[j].real()+eps)-in[i].d[j].real())>eps){
	  //cout <<"invalid " << i <<" coordinate real"<<endl;
	  return false;
	}
      }else {
	if (abs(ceil(in[i].d[j].real()-eps)-in[i].d[j].real())>eps){
	  //	  cout <<"invalid " << i <<" coordinate real"<<endl;
	  return false;
	}
      }
      if (in[i].d[j].imag()>=0){
	if (abs(floor(in[i].d[j].imag()+eps)-in[i].d[j].imag())>eps){
	  //	  cout <<"invalid " << i <<" " << j << " coordinate imag"<<endl;
	  return false;
	}
      }else {
	if (abs(ceil(in[i].d[j].imag()-eps)-in[i].d[j].imag())>eps){
	  //  cout <<"invalid " << i <<" " << j << " coordinate imag"<<endl;
	  return false;
	}
      }
    }
  }
  REP(i,1,4){
    if (isp(in[i].d[0],in[i].d[1],in[i].d[2])||
	isp(in[i].d[0],in[i].d[2],in[i].d[1])||
	isp(in[i].d[1],in[i].d[2],in[i].d[0])){
      //      cout <<"invalid " << i <<" is on it self " << endl;
      return false;
    }
    rep(j,4){
      if (i == j)continue;

      if (j != 0 && abs(in[i].d[2]-in[j].d[2])<1e-8)return false;

      if (is_in(in[j].d,in[i].d[2])){
	//	cout <<"invalid " << i <<" is in " << j << endl;
	return false;
      }
      rep(k,3){
	if (isp(in[j].d[k],in[j].d[(k+1)%3],in[i].d[2])){
	  //	  cout <<"invalid " << i <<" is on " << in[j].d[k]<<in[j].d[(k+1)%3]
	  //	       <<endl;
	  return false;
	}
	if (is_intersected_ls(in[i].d[0],in[i].d[2],
			     in[j].d[k],in[j].d[(k+1)%3])){
	  //	  cout << "invalid " << i <<" intersected " << 
	  //	    in[i].d[0] <<in[i].d[2] <<"-"<< in[j].d[k]<<in[j].d[(k+1)%3]<<endl;
	  return false;
	}
	if (is_intersected_ls(in[i].d[1],in[i].d[2],
			     in[j].d[k],in[j].d[(k+1)%3])){
	  //	  cout << "invalid " << i <<" intersected " << 
	  //	    in[i].d[1] <<in[i].d[2] <<"-"<< in[j].d[k]<<in[j].d[(k+1)%3]<<endl;
	  return false;
	}
      }
    }
  }
  return true;
}


void decide3(Tri in[4],double dist2){
  double dist1=compute_dist(in[1].d[0].real()-in[1].d[2].real(),
		    in[1].d[0].imag()-in[1].d[2].imag());
  P c1=in[3].d[1];
  P c2=in[3].d[0];

  if (is_intersected_circle(c1,c2,dist1,dist2) == 2){
    pair<P,P> tmp=CC_intersection(c1,c2,dist1,dist2);
    in[3].d[2]=tmp.first;
    if (isvalid(in))compute_height(in);
    //if (isvalid(in))cout <<"valid"<<endl;
    //    else cout << "invalid"<<endl;
    //    compute_height(in);
    in[3].d[2]=tmp.second;
    if (isvalid(in))compute_height(in);
    //if (isvalid(in))cout <<"valid"<<endl;
    //    else cout << "invalid"<<endl;
    //    compute_height(in);
  }
}

void decide2(Tri in[4]){
  double dist = compute_dist(in[1].d[1].real()-in[1].d[2].real(),
			     in[1].d[1].imag()-in[1].d[2].imag());
  int lim = (int)floor(dist);
  for(int x=-(int)floor(dist);x <= lim;x++){
    double y = sqrt(dist*dist-x*x+eps);
    //    cout << x <<" " << y <<" " << floor(y) <<" " <<y << endl;
    if ( (y>0&&abs(floor(y)-y)<eps)){
      //      cout <<"now "<<endl;
      
      in[2].d[2].real()=in[2].d[0].real()+x;
      in[2].d[2].imag()=in[2].d[0].imag()+y;
      double dist2 = compute_dist(in[2].d[2].real()-in[2].d[1].real(),
				  in[2].d[2].imag()-in[2].d[1].imag());
      decide3(in,dist2);
      in[2].d[2].real()=in[2].d[0].real()+x;
      in[2].d[2].imag()=in[2].d[0].imag()-y;
      dist2 = compute_dist(in[2].d[2].real()-in[2].d[1].real(),
			   in[2].d[2].imag()-in[2].d[1].imag());
      decide3(in,dist2);
    }
  }
}

void decide1(Tri in[4]){
  REP(y,-100,101){
    REP(x,-100,101){
  //  REP(y,-10,10){
  //  REP(x,-10,10){
	//	cout << "output " << x <<" " << y << endl;
      in[1].d[2].real()=x;
      in[1].d[2].imag()=y;
      decide2(in);
    }
  }
}

main(){
  Tri in[4];
  while(cin>>in[0].d[0].real()>>in[0].d[0].imag()
	>>in[0].d[1].real()>>in[0].d[1].imag()
	>>in[0].d[2].real()>>in[0].d[2].imag()){
    if (in[0].d[0].real() == 0 && in[0].d[0].imag() == 0 &&
	in[0].d[1].real() == 0 && in[0].d[1].imag() == 0 &&
	in[0].d[2].real() == 0 && in[0].d[2].imag() == 0)break;
    in[1].d[0]=in[0].d[0];
    in[1].d[1]=in[0].d[1];

    in[2].d[0]=in[0].d[1];
    in[2].d[1]=in[0].d[2];
    
    in[3].d[0]=in[0].d[2];
    in[3].d[1]=in[0].d[0];

    ans = 1e100;
    decide1(in);
    if (ans >1e99)printf("-1\n");
    else printf("%.5lf\n",ans);
  }
}

Compiler output:
a.cc: In function 'P vector_mapping(P, P, P)':
a.cc:80:3: error: 'assert' was not declared in this scope
   80 |   assert(!(isnan(C)));
      |   ^~~~~~
a.cc:4:1: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
    3 | #include<cmath>
  +++ |+#include <cassert>
    4 | using namespace std;
a.cc: In function 'void decide2(Tri*)':
a.cc:290:22: error: lvalue required as left operand of assignment
  290 |       in[2].d[2].real()=in[2].d[0].real()+x;
      |       ~~~~~~~~~~~~~~~^~
a.cc:291:22: error: lvalue required as left operand of assignment
  291 |       in[2].d[2].imag()=in[2].d[0].imag()+y;
      |       ~~~~~~~~~~~~~~~^~
a.cc:295:22: error: lvalue required as left operand of assignment
  295 |       in[2].d[2].real()=in[2].d[0].real()+x;
      |       ~~~~~~~~~~~~~~~^~
a.cc:296:22: error: lvalue required as left operand of assignment
  296 |       in[2].d[2].imag()=in[2].d[0].imag()-y;
      |       ~~~~~~~~~~~~~~~^~
a.cc: In function 'void decide1(Tri*)':
a.cc:310:22: error: lvalue required as left operand of assignment
  310 |       in[1].d[2].real()=x;
      |       ~~~~~~~~~~~~~~~^~
a.cc:311:22: error: lvalue required as left operand of assignment
  311 |       in[1].d[2].imag()=y;
      |       ~~~~~~~~~~~~~~~^~
a.cc: At global scope:
a.cc:317:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  317 | main(){
      | ^~~~
a.cc: In function 'int main()':
a.cc:319:12: error: no match for 'operator>>' (operand types are 'std::istream' {aka 'std::basic_istream<char>'} and 'double')
  319 |   while(cin>>in[0].d[0].real()>>in[0].d[0].imag()
      |         ~~~^~~~~~~~~~~~~~~~~~~
      |         |                   |
      |         |                   double
      |         std::istream {aka std::basic_istream<char>}
In file included from /usr/include/c++/14/iostream:42,
                 from a.cc:1:
/usr/include/c++/14/istream:170:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  170 |       operator>>(bool& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:170:7: note:   conversion of argument 1 would be ill-formed:
a.cc:319:29: error: cannot bind non-const lvalue reference of type 'bool&' to a value of type 'double'
  319 |   while(cin>>in[0].d[0].real()>>in[0].d[0].imag()
      |              ~~~~~~~~~~~~~~~^~
/usr/include/c++/14/istream:174:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char; _Traits = std::char_traits<char>]' (near match)
  174 |       operator>>(short& __n);
      |       ^~~~~~~~
/usr/include/c++/14/istream:174:7: note:   conversion of argument 1 would be ill-formed:
a.cc:319:29: error: cannot bind non-const lvalue reference of type 'short int&' to a value of type 'double'
  319 |   while(cin>>in[0].d[0].real()>>in[0].d[0].imag()
      |              ~~~~~~~~~~~~~~~^~
/usr/include/c++/14/istream:177:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  177 |       operator>>(unsigned short& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:177:7: note:   conversion of argument 1 would be ill-formed:
a.cc:319:29: error: cannot bind non-const lvalue reference of type 'short unsigned int&' to a value of type 'double'
  319 |   while(cin>>in[0].d[0].real()>>in[0].d[0].imag()
      |              ~~~~~~~~~~~~~~~^~
/usr/include/c++/14/istream:181:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char; _Traits = std::char_traits<char>]' (near match)
  181 |       operator>>(int& __n);
      |       ^~~~~~~~
/usr/include/c++/14/istream:181:7: note:   conversion of argument 1 would be ill-formed:
a.cc:319:29: error: cannot bind non-const lvalue reference of type 'int&' to a value of type 'double'
  319 |   while(cin>>in[0].d[0].real()>>in[0].d[0].imag()
      |              ~~~~~~~~~~~~~~~^~
/usr/include/c++/14/istream:184:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  184 |       operator>>(unsigned int& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:184:7: note:   conversion of argument 1 would be ill-formed:
a.cc:319:29: error: cannot bind non-const lvalue reference of type 'unsigned int&' to a value of type 'double'
  319 |   while(cin>>in[0].d[0].real()>>in[0].d[0].imag()
      |              ~~~~~~~~~~~~~~~^~
/usr/include/c++/14/istream:188:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  188 |       operator>>(long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:188:7: note:   conversion of argument 1 would be ill-formed:
a.cc:319:29: error: cannot bind non-const lvalue reference of type 'long int&' to a value of type 'double'
  319 |   while(cin>>in[0].d[0].real()>>in[0].d[0].imag()
      |              ~~~~~~~~~~~~~~~^~
/usr/include/c++/14/istream:192:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  192 |       operator>>(unsigned long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:192:7: note:   conversion of argument 1 would be ill-formed:
a.cc:319:29: error: cannot bind non-const lvalue reference of type 'long unsigned int&' to a value of type 'double'
  319 |   while(cin>>in[0].d[0].real()>>in[0].d[0].imag()
      |              ~~~~~~~~~~~~~~~^~
/usr/include/c++/14/istream:199:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  199 |       operator>>(long long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:199:7: note:   conversion of argument 1 would be ill-formed:
a.cc:319:29: error: cannot bind non-const lvalue reference of type 'long long int&' to a value of type 'double'
  319 |   while(cin>>in[0].d[0].real()>>in[0].d[0].imag()
      |              ~~~~~~~~~~~~~~~^~
/usr/include/c++/14/istream:203:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  203 |       operator>>(unsigned long long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:203:7: note:   conversion of argument 1 would be ill-formed:
a.cc:319:29: error: cannot bind non-const lvalue reference of type 'long long unsigned int&' to a value of type 'double'
  319 |   while(cin>>in[0].d[0].real()>>in[0].d[0].imag()
      |              ~~~~~~~~~~~~~~~^~
/usr/include/c++/14/istream:219:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(float&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  219 |       operator>>(float& __f)
      |       ^~~~~~~~
/usr/include/c++/14/istream:219:7: note:   conversion of argument 1 would be ill-formed:
a.cc:319:29: error: cannot bind non-const lvalue reference of type 'float&' to a value of type 'double'
  319 |   while(cin>>in[0].d[0].real()>>in[0].d[0].imag()
      |              ~~~~~~~~~~~~~~~^~
/usr/include/c++/14/istream:223:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(double&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  223 |       operator>>(double& __f)
      |       ^~~~~~~~
/usr/include/c++/14/istream:223:7: note:   conversion of argument 1 would be ill-formed:
a.cc:319:29: error: cannot bind non-const lvalue reference of type 'double&' to an rvalue of type 'double'
  319 |   while(cin>>in[0].d[0].real()>>in[0].d[0].imag()
      |              ~~~~~~~~~~~~~~~^~
/usr/include/c++/14/istream:227:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long double&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  227 |       operator>>(long double& __f)
      |       ^~~~~~~~
/usr/include/c++/14/istream:227:7: note:   conversion of argument 1 would be ill-formed:
a.cc:319:29: error: cannot bind non-const lvalue reference of type 'long double&' to a value of type 'double'
  319 |   while(cin>>in[0].d[0].real()>>in[0].d[0].imag()
      |              ~~~~~~~~~~~~~~~^~
/usr/include/c++/14/istream:328:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]'
  328 |       operator>>(void*& __p)
      |       ^~~~~~~~
/usr/include/c++/14/istream:328:25: note:   no known conversion for argument 1 from 'double' to 'void*&'
  328 |       operator>>(void*& __p)
      |                  ~~~~~~~^~~
/usr/include/c++/14/istream:122:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(__istream_type& (*)(__istream_type&)) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std: