The Best Tower

Whats the constraint on radius of tower?

I think the real question is, “What are the constraints on the coordinates?” My understanding is that -2 and -1 are not “between 0 and 10000 (inclusive)”.

@Manu It looks like there is no constraint, except that the tower cannot overlap any of the given buildings. This should be clarified though.

I believe that you need to parse

"The distance between a point and a circle is defined to be the difference between the distance from the circle's center to the point and the circle's radius."

as follows;

The distance ... is defined to be

[the difference between

{the distance from the circle's center to the point}

and {the circle's radius.}]

This seems to work for the example and places a constraint on the tower's radius.

I would like to see a constraint on R as well. (Plus fixing the test case or constraints on input points.)

Actually, the question itself doesn't specify whether the tower can contain buildings. Which isn't necessarily a silly question, since a tower could easily be built above buildings. So I would like that clarified too.

Scoring seems to be broken too. Everyone is getting 0 points.

do we have to print a new line after inputting number of test cases??

it doesnt say so in the problem statement but appears to be like that in the given example.

Please clarify. Thanks.

sorry, i'd like to reframe my previous query.

is there a new line to be read after we read the number of test cases T ??

it doesnt say so in the problem statement but appears to be like that in the given example.

Please clarify. Thanks.

Checking the issue related to scoring. Internally it's working, it's being displayed as 0. So you may continue making submissions.

Checking the problem statement and constraints as well.

As a general point, the submission system itself seems to be acting up - I seem to get internal error the first submission to a problem; every submission after that, I'm seeing the result of the *previous* submission. Had me very confused for a while..

The scoring issue is fixed. Please let me know if you are facing problems related to it.

@Stephen Will check this. The 'My Submissions' page still displays the correct results. You can check status on that page till this is resolved.

what is squared distance. is it the square of distance?

IMPORTANT:

@All

R is between 0 and 10000 (inclusive) too

Now the 'my submissions' scores are right but the scoreboard has everyone on 0 for this problem ;)

@Stephen. There is some issue with the DB which should be resolved soon.

still the score to this problem is showing zero

Sample output is not the best tower that could be built, is it? Are you sure that there can be buildings inside tower?

Nobody said the sample output was optimal. This is a challenge problem; being optimal is not the point.

Slight wording problem:

"output 3 numbers (X,Y) and R, rounded to 3 decimal digits"

should be something like:

"output 3 numbers (X,Y) and R that have up to 3 decimal digits after the decimal point"

The first formulation says that the numbers I put in the output are not necessarily my actual answer, but an approximation of the answer. This means that the judge has no way of checking correctness, since it does not know the actual exact answer that might be correct while the rounded approximation isn't.

By the way - since we have no test cases to verify solutions after the contest - I want to make sure that the checker actually verifies correctness exactly. That is, points on the secure circle are allowed, points even slightly outside the secure circle are rejected (using exact arithmetic), coordinates with more than 3 digits after decimal point are rejected.

@Tomek The numbers you put in your output are your answer, by definition. I don't understand your comment.

What is total square distance? Sum of squared distances or is it squared sum of distances?

@Brian

I guess I wasn't clear. The problem is that the problem doesn't ask you to print X, Y, R. It asks you to print r(X), r(Y), r(R), where r(a) = a rounded to 3 decimal digits. But the constraints are on X,Y,R and not on r(X), r(Y), r(R). Therefore the judge has no way of verifying constraints or scoring, because it doesn't know what your X,Y,R are, since these are not in the output.

Example: suppose (Xs,Ys)=0, Rs=1. You find a valid tower (X,Y,R) = (0.9999, 0.001, 1). The output contains r(X), r(Y), r(R) = 1, 0.001, 1. The judge has no way of verifying whether X,Y lies inside the secure circle, because it only knows r(X), r(Y).

I don't think in this problem, my output needs to be matched with expected output exactly.Then what is the meaning of getting "wrong answer" after submitting the solution?

Wrong answer means your answer is not valid; which (unless you have done something like output a negative radius, or used the wrong input format) probably means your center is not within the secure circle.

my radius is positive ,input format is correct,center is with in the secure circle.What else the problems could be?

That's about it, other than perhaps not rounding answers to 3dp. Don't forget, as Tomek mentioned above, perhaps you think your point is in the secure circle, but after rounding to 3dp it isn't. Happened to me at one point.

@ dileep radius of tower circle should also be less than 1000 as menioned by annirudh..

Can anybody explain me how the sample output's score 0.023444 has been calculated???

Thankx for ur suggestions ,and last problem ,is there any specific format for output,like now I am giving it with tab spaces (x{r} tab y{r} tab r} ,is it right?

@dileepkumar

You simply have to give one space between each x(r) ,y(r) and  r

sample output

1.234 3.456 4.567

Thanx all for ur suggesions,and my main problem is

In Dev c++ ,cout.precison(4),is giving 3 digits after decimal place,Got it corrected

The ranking is faulty.

Those who submitted 3 problems have been assigned the score of 4; seems Strange

How exactly the distance is calculated between a point & a circle?

I don't understand what ot do with radius?

The distance between a point and a circle in this problem is defined to be the absolute value of the difference between the radius of the circle and the distance from the point to the center of the circle.  In other words, let D be the distance from the point to the center of the circle and R be the circle's radius.  The distance from the point to the circle is now abs(D-R).

Did anybody verify that it's impossible to do better than 1.563631? I used gradient descent (kinda), starting at a few different points, but there's no guarantee that my algorithm would always find the best possible solution.

My brute forcer gave the solution 1.563817 (very close to the best possible) :)

I think the test data for this problem should be given out

hello,

what is the optimal solution for this problem? the simple n straightforward brute force comes close , though isnt the best 1.....

also, given a totally different input set, would all optimal solutions ( i.e. those that fetched 1.000000 pts) still give the same answer?

Given that you know the center of the tower, you can easily prove that the optimal radius is the average distance from the center to each point. After that, any sort of hillclimbing algorithm will lead to the best center.

CodeChef submission 210202 (C++ 4.3.2) plaintext list. Status: AC, problem NX, contest MARCH10. By yayamao (yayamao), 2010-03-13 14:59:45.
#include<cmath>
#include<cstdio>
 
#define MAX_POINT_NUMBER 100
 
#define EPS 1E-9
#define INF 1E99
 
struct Point
{
	double x,y;
 
	inline Point(){}
	inline Point(double x,double y):x(x),y(y){}
	inline ~Point(){}
};
 
struct Circle
{
	Point o;
	double r;
 
	inline Circle(){}
	inline Circle(Point o,double r):o(o),r(r){}
	inline ~Circle(){}
};
 
inline double squaredDistance(const Point &a,const Point &b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
 
inline bool contain(const Circle &c,const Point &p)
{
	return squaredDistance(c.o,p)<=c.r*c.r;
}
 
Circle secureCircle;
 
int n;
Point p[MAX_POINT_NUMBER];
 
Circle tower;
double minTotalDistance;
 
void readData()
{
	scanf("%lf %lf %lf",&secureCircle.o.x,&secureCircle.o.y,&secureCircle.r);
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%lf %lf",&p[i].x,&p[i].y);
}
 
double search(const Point &o,double &totalDist)
{
	double D=0,D2=0;
	for(int i=0;i<n;i++)
	{
		double distPower=squaredDistance(o,p[i]);
		D+=sqrt(distPower);
		D2+=distPower;
	}
	totalDist=(n*D2-D*D)/n;
	return D/n;
}
 
void solve()
{
	tower.o=secureCircle.o;
	tower.r=search(tower.o,minTotalDistance);
 
	double delta=secureCircle.r;
 
	while(delta>0.0005)
	{
		while(true)
		{
			bool loop=true;
			for(int dx=-8;dx<=8;dx++) for(int dy=-8;dy<=8;dy++)
			{
				Point newO=Point(secureCircle.o.x+dx*delta-EPS,secureCircle.o.y+dy*delta-EPS);
				if(!contain(secureCircle,newO)) continue;
				double dist;
				double r=search(newO,dist);
				if(dist<minTotalDistance)
				{
					minTotalDistance=dist;
					tower=Circle(newO,r);
					//loop=false;
				}
			}
			if(loop) break;
		}
		delta*=0.9;
	}
	printf("%.3lf %.3lf %.3lfn",tower.o.x,tower.o.y,tower.r);
}
 
int main()
{
	//freopen("in","r",stdin);
 
	int T;
	scanf("%d",&T);
	while(T--)
	{
		readData();
		solve();
	}
 
	return 0;
}