Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
The Best Tower CodeChef Solution
Problem -The Best Tower CodeChef Solution
“This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
The Best Tower CodeChef Solution in C++17
“#include <stdio.h>
#include<stdlib.h>
#include <math.h>
double dist(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
typedef struct
{
double x,y;
} P;
P a[100];
int main()
{
int T,N, i;
double X,Y,R,d,t,x,y;
scanf("%d",&T);
while(T--)
{
scanf("%lf %lf %lf %d",&X,&Y,&R,&N);
for(x=y=i=0;i<N;++i)
scanf("%lf %lf",&a[i].x,&a[i].y),x+=a[i].x,y+=a[i].y;
x/=N,y/=N;
t=R-0.001;
if((d=dist(x,y,X,Y))>t)
x=X-(t/d*(X-x)),y=Y-(t/d*(Y-y));
for(d=i=0;i<N;++i)
d+=dist(x,y,a[i].x,a[i].y);
d/=N;
printf("%.3lf %.3lf %.3lf\n",x,y,d);
}
return 0;
}The Best Tower CodeChef Solution in C++14
“ #include <stdio.h>
#include<iostream>
using namespace std;
int main()
{
int t;
int x, y, redius;
int n;
int i;
int x1, y1;
scanf("%d", &t);
while (t--)
{
cin>>x>>y>>redius;
cin>>n;
for (i = 0; i < n; i++)
scanf("%d%d", &x1, &y1);
printf("%d.000 %d.000 %d.000\n", x, y, redius);
}
return 0;
} The Best Tower CodeChef Solution in C
“#include<stdio.h>
int main()
{
int t,a,b,c,n,i,x1,x2;
scanf("%d",&t);
while(t>0)
{
scanf("%d%d%d",&a,&b,&c);
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d",&x1,&x2);
printf("%d.000 %d.000 %d.000\n",a,b,c);
t--;
}
return 0;
} The Best Tower CodeChef Solution in JAVA
“import java.io.*;
import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.*;
public class Main {
static interface F{
double f(double a, double b);
}
static interface Opt{
double[] optimize(double a, double b, double r, F f);
}
static double eps = 0.00001;
static double[] grad(double a, double b, F f){
double z = f.f(a,b);
return new double[]{(f.f(a+eps, b)-z)/eps,(f.f(a, b+eps)-z)/eps};
}
static double[] hess(double a, double b, F f){
double z00 = f.f(a,b);
double z10 = f.f(a+eps,b);
double z01 = f.f(a,b+eps);
double z11 = f.f(a+eps,b+eps);
double z20 = f.f(a+eps*2,b);
double z02 = f.f(a,b+eps*2);
return new double[]{
(z20+z00-2*z10)/(eps*eps),
(z02+z02-2*z01)/(eps*eps),
(z11+z00-z01-z10)/(eps*eps)
};
}
static double distToR(double[] aa, double[] bb, double r){
double a = aa[0];
double b = aa[1];
double x = bb[0];
double y = bb[1];
if(Math.abs(x)<eps && Math.abs(y)< eps){
return r*.99;
}
double disc = (r*r-a*a)*y*y+(r*r-b*b)*x*x + 2*a*b*x*y;
return (Math.sqrt(disc)-a*x-b*y)/(x*x+y*y);
}
static double[] inv(double[] h, double[] g) {
double det = h[0]*h[2] -h[1]*h[1];
double a = (h[2]*g[0]-h[1]*g[1])/det;
double b = (h[0]*g[1]-h[1]*g[0])/det;
return new double[]{a,b};
}
static class Newton implements Opt{
F f;
double r;
double rr;
public double[] optimize(double a, double b, double r, F f) {
this.f = f;
this.r = r;
rr = r*r;
double[] x = new double[]{a,b};
while(true){
double[] w = nextStep(x);
if(Double.isNaN(w[0])|| Double.isNaN(w[1])){
return new double[]{0,0};
}
double k = w[0]*w[0]+w[1]*w[1];
if(k >=rr){
double sk = Math.sqrt(k/rr);
w[0]/=sk;
w[1]/=sk;
}
if(dist2(w,x)<eps*eps){
return(w);
}
x = w;
}
}
private double[] nextStep(double[] x) {
double[] g = grad(x[0],x[1],this::fun);
double[] h = hess(x[0],x[1],this::fun);
double trace = h[0]+h[2];
double det = h[0]*h[2]-h[1]*h[1];
double[] dir = null;
if(trace < 0 || det <= 0){
dir = Arrays.copyOf(g, 2);
double k = distToR(x, g, r);
dir[0] *=k;
dir[1] *=k;
}
else{
if(trace*trace/det >400){
h[0] += trace/20;
h[0] += trace/20;
}
dir = inv(h,g);
}
dir[0] = -dir[0];
dir[1] = -dir[1];
return lineSearch(x, dir, g, this::fun, 0.2);
}
double fun(double a,double b){
double k = a*a+b*b;
if(k >=rr){
double sk = Math.sqrt(k/rr);
a/=sk;
b/=sk;
}
return f.f(a, b);
}
}
static double[] lineSearch(double[] x, double[]d, double[] g, F f, double c){
double f0 = f.f(x[0], x[1]);
double k = (dot(g,d));
double a = 2;
double val = 0;
int count = 0;
do{
count++;
a /= 2;
val = f.f(x[0]+a*d[0],x[1]+a*d[1]);
if(count > 200)
return x;
}while(val > f0 + a*c*k);
return new double[]{x[0]+a*d[0],x[1]+a*d[1]};
}
static double dist2(double[] w, double[] x) {
double a = w[0]-x[0];
double b = w[1]-x[1];
return a*a+b*b;
}
private static double dot(double[] a, double[] b) {
return a[0]*b[0] + a[1]*b[1];
}
static class Problem{
int[]x;
int[]y;
int[]C;
long R;
int n;
@Override
public String toString() {
return "Problem [x=" + Arrays.toString(x) + ", y=" + Arrays.toString(y)
+ ", C=" + Arrays.toString(C) + ", R=" + R + ", n=" + n + "]";
}
public Problem(int[] xx, int[] yy, int[] C, int R) {
n = xx.length;
this.R = R;
this.C = C;
this.x = Arrays.copyOf(xx, n);
this.y = Arrays.copyOf(yy, n);
for(int i=0; i<n; ++i){
x[i]-=C[0];
y[i]-=C[1];
}
}
double value(double a, double b){
double rsum = 0;
double r2sum = 0;
for(int i=0; i<n; ++i){
double xx = a-x[i];
double yy = b-y[i];
double r = xx*xx+yy*yy;
r2sum += r;
rsum += Math.sqrt(r);
}
return r2sum - rsum*rsum/n;
}
double getRadius(double a, double b){
double rsum = 0;
for(int i=0; i<n; ++i){
double xx = a-x[i];
double yy = b-y[i];
double r = xx*xx+yy*yy;
rsum += Math.sqrt(r);
}
return rsum/n;
}
double[] solve(Opt o, long t){
long tmax = System.currentTimeMillis() + t;
double min = Double.MAX_VALUE;
Random r = new Random();
double[] best = new double[]{0,0};
while(System.currentTimeMillis() < tmax){
double a = 1;
double b = 1;
while(a*a + b*b >1){
a = r.nextDouble()*2-1;
b = r.nextDouble()*2-1;
}
double[] temp = o.optimize(a,b, R, this::value);
double v = value(temp[0],temp[1]);
if(v<min){
min = v;
best = temp;
}
}
double rr = Math.sqrt(best[0]*best[0] + best[1]*best[1]);
if(rr > R){
best[0]*=R/rr;
best[1]*=R/rr;
}
best[0] = Math.round(best[0]*1000)/1000.0;
best[1] = Math.round(best[1]*1000)/1000.0;
double[] temp = Arrays.copyOf(best, best.length);
double score = Double.MAX_VALUE;
for(int i=-2; i<=2; ++i){
for(int j=-2; j<=2; ++j){
double a = best[0]+i*0.001;
double b = best[1]+j*0.001;
if(a*a + b*b > R*R-eps)
continue;
double v = value(a,b);
if(v < score){
temp[0] = a;
temp[1] = b;
score = v;
}
}
}
return new double[]{temp[0]+C[0],temp[1]+C[1],getRadius(temp[0],temp[1])};
}
}
static int[] getInts(BufferedReader br) throws IOException{
String[] ss = new String[0];
while(ss.length==0 || "".equals(ss[0])) ss = br.readLine().split(" ");
// trace(0,Arrays.toString(ss));
int[] ret = new int[ss.length];
for(int i=0; i<ss.length; ++i){
ret[i] = Integer.parseInt(ss[i]);
}
return ret;
}
static Problem readProblem(BufferedReader br) throws IOException{
int[] k = getInts(br);
int[] C = new int[]{k[0],k[1]};
int R = k[2];
int n = getInts(br)[0];
int[] x = new int[n];
int[] y = new int[n];
for(int i=0; i<n; ++i){
k = getInts(br);
x[i] = k[0];
y[i] = k[1];
}
return new Problem(x, y, C, R);
}
static void goFile(String s) throws NumberFormatException, FileNotFoundException, IOException{
go(new FileReader(new File(s)));
}
static void go() throws NumberFormatException, IOException{
go(new InputStreamReader(System.in));
}
static final NumberFormat format = new DecimalFormat("#0.000");
static void go(Reader r) throws IOException{
BufferedReader br = new BufferedReader(r);
int x = getInts(br)[0];
for(int i=0; i<x; ++i){
double[] z = readProblem(br).solve(new Newton(), 100);
for(double y : z){
System.out.print(format.format(y) + " ");
}
System.out.println();
}
}
static Problem randomProblem(int n, int cx, int cy, int r){
int[] x = new int[n];
int[] y = new int[n];
Random rr = new Random();
for(int i=0; i<n; ++i){
x[i] = rr.nextInt(100000);
y[i] = rr.nextInt(100000);
}
return new Problem(x, y, new int[]{cx, cy},r);
}
public static void main(String[] args) throws NumberFormatException, IOException {
go();
}
}The Best Tower CodeChef Solution Review:
In our experience, we suggest you solve this The Best Tower CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the The Best Tower CodeChef Solution.
Conclusion:
I hope this The Best Tower CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
