#include #include using namespace std; using namespace atcoder; typedef long long int ll; typedef long double ld; typedef vector vi; typedef vector vvi; typedef vector vvvi; typedef vector vvvvi; typedef pair pi; typedef pair ppi; typedef pair pppi; typedef pair ppppi; #define FOR(i,l,r) for(ll i=l;i=l;i--) #define RREP(i,n) RFOR(i,0,n) #define ALL(x) x.begin(),x.end() #define F first #define S second #define BS(A,x) binary_search(ALL(A),x) #define LB(A,x) (ll)(lower_bound(ALL(A),x)-A.begin()) #define UB(A,x) (ll)(upper_bound(ALL(A),x)-A.begin()) #define COU(A,x) (UB(A,x)-LB(A,x)) #define sz(c) ((ll)(c).size()) templateusing min_priority_queue=priority_queue,greater>; templateostream&operator<<(ostream&os,pair&p){os<istream&operator>>(istream&is,pair&p){is>>p.F>>p.S;return is;} templateostream&operator<<(ostream&os,vector&v){REP(i,sz(v))os<istream&operator>>(istream&is,vector&v){for(T&in:v)is>>in;return is;} templatebool chmax(T&a,T b){if(abool chmin(T&a,T b){if(b vm; typedef vector vvm; typedef vector vvvm; typedef vector vvvvm; ostream&operator<<(ostream&os,mint&a){os<>N; vi X(N),Y(N),T(N); REP(i,N)cin>>X[i]>>Y[i]>>T[i]; vvi D(N,vi(N)); REP(i,N)REP(j,N){ if(T[i]==T[j])D[i][j]=(X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]); else{ ll a=4*(X[i]*X[i]+Y[i]*Y[i])*(X[j]*X[j]+Y[j]*Y[j]); ll t=sqrt(a)-10; while(t<0||t*t<=a)t++;t--; D[i][j]=X[i]*X[i]+Y[i]*Y[i]+X[j]*X[j]+Y[j]*Y[j]-t; } } ll l=-1,r=1e18; while(r-l>1){ ll m=(l+r)/2; dsu d(N); REP(i,N)REP(j,N)if(D[i][j]<=m)d.merge(i,j); if(d.same(0,N-1))r=m;else l=m; } cout<