11281 - Triangular Pegs in Round Holes

[hamedv]

what's wrong with my code

can any one help me

Code: Select all

#include <iostream>
#include <cmath>

using namespace std;

int n, m;
double d[105], a, b, c, s, k;

#define EPS -(1e-9)

int main()
{
	cin >> m;
	for (int i = 0; i < m; i++)
		cin >> d[i];
	cin >> n;
	for (int j = 0; j < n; j++)
	{
		cin >> a >> b >> c;
		k = (a + b + c) / 2;
		s = sqrt(k * (k - a) * (k - b) * (k - c));
		k = (a * b * c) / 2 / s;
		bool g = 0;
		for (int i = 0; i < m; i++)
			if (d[i] - k > EPS)
				if (g)
					cout << " " << i+1;
				else
					cout << "Peg " << char(j + 'A') << " will fit into hole(s): " << i + 1, g = true;
		if (!g)
			cout << "Peg " << char(j + 'A') << " will not fit into any holes";
		cout << endl;
	}
}

thanks in advance[/code]

[iran]

I used same approach but wa.

Code: Select all

// In the name of God

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

#define eps 1e-7

double hole[100];

int main ()
{
	int n, nh, i, j;
	double a, b, c, k, R;
	cin >> nh;
	for( i = 0; i < nh; i++ )
		cin >> hole[i];

	cin >> n;
	for( i = 0; i < n; i++ )
	{
		cin >> a >> b >> c;
		k = (a+b+c)/2.;
		k = sqrt( k*(k-a)*(k-b)*(k-c) );
		R = (a * b * c)/(2 * k);//R is Diameter of smallest circle that bounds the triangle
		
		vector< int > fits;
		
		for( j = 0; j < nh; j++ )
		{
			if( R < hole[j] || fabs( hole[j] - R ) < eps )
				fits.push_back( j + 1 );
		}
		
		if( fits.size() != 0 )
		{
			cout << "Peg " << (char)(i+'A') << " will fit into hole(s):";
			for( j = 0; j < fits.size(); j++ )
				cout << " " << fits[j];
		}
		else
			cout << "Peg " << (char)(i+'A') << " will not fit into any holes";
		
		cout << endl;
	}
	return 0;
}

[Darko]

I'll just say that those solve certain cases, but not all. A lot of people made the same assumption.

[Robert Gerbicz]

I'll just say that those solve certain cases, but not all. A lot of people made the same assumption.

You are right. Here is a tricky case, including correct output ( this can be also critical input if you are not using a small epsilon in your program ):

Code: Select all

1
100.0
1
51.0 51.0 100.0
Peg A will fit into hole(s): 1

[hamedv]

can you tell me why my code gives wrong answer to your input?
is my formula wrong?

[Robert Gerbicz]

can you tell me why my code gives wrong answer to your input?
is my formula wrong?

Yes, that method is wrong.

[iran]

Your output is wrong can you explain how can 51 51 100 fit into a circle with diameter 100.
i think the correct output is : "Peg A will not fit into any holes" .

please see link below i depict the testcase.

http://www.sharemation.com/taksavar7/ci ... niq=2qpocc

[iran]

1
100.0
1
51.0 51.0 100.0
Peg A will fit into hole(s): 1

Your output is wrong can you explain how can 51 51 100 fit into a circle with diameter 100.
i think the correct output is : "Peg A will not fit into any holes" .

please see link below i depict the testcase.

http://www.sharemation.com/taksavar7/ci ... niq=2qpocc

[Robert Gerbicz]

Your output is wrong can you explain how can 51 51 100 fit into a circle with diameter 100.
i think the correct output is : "Peg A will not fit into any holes" .

please see link below i depict the testcase.

http://www.sharemation.com/taksavar7/ci ... niq=2qpocc

That's wrong. By Pithagoras formula:
m=sqrt(51^2-50^2)=10.0498756 and not 71.42

In my test case the 100.0 length side of the triangle is the diameter of the round hole.

[iran]

Oh right, (sorry i have mistake ) you are correct i found why this code got wa thank you very much but what is the correct method to solve it?

thanks again.

[baodog]

I try the following...

Code: Select all

      
      bool leq(long double a, long double b)
      {return (a<b || (a-b < eps &&b-a < eps));}

      s = (a+b+c)/2;
      D = 1e100;
      Area = sqrt(s*(s-a)*(s-b)*(s-c)); 
      if(Area>1e-20) D = (a*b*c)/(2*Area); else while(1) cout << "error";
      h = Area*2.0/a; if(leq(2*h,a)) D = min(D,a); 
      h = Area*2.0/b; if(leq(2*h,b)) D = min(D,b); 
      h = Area*2.0/c; if(leq(2*h,c)) D = min(D,c); 

To compute the minimum diameter... but it gets WA...
There seems to be no numerical bounds on the floating point numbers.
Or proper statement about what EPS value is correct.
Technically you can create data to fail any program...
It becomes a guessing game.

[Darko]

Please post your solution and I'll tell you where it fails. It will have to wait unitl 4am MST, I am going to work now.

Btw, why not just return (a<b+eps) for that leq?

[Robert Gerbicz]

I try the following...
To compute the minimum diameter... but it gets WA...

In fact for this problem on the contest I haven't calculated the minimum diameter. It is only need to check for each circle if it is good or not.

[Darko]

baodog, why do you think that approach works? I might be too tired to think straight, but I think it does not work for sqrt(5), sqrt(2), 1 ((0,0),(2,1),(1,0)). I think that piece of code returns sqrt(2) - which would be true for the sqrt(2),1,1 triangle with the same area.

I see you got AC in the meantime, was it with this approach?

[Robert Gerbicz]

baodog, why do you think that approach works? I might be too tired to think straight, but I think it does not work for sqrt(5), sqrt(2), 1 ((0,0),(2,1),(1,0)). I think that piece of code returns sqrt(2) - which would be true for the sqrt(2),1,1 triangle with the same area.

I see you got AC in the meantime, was it with this approach?

I also think that's incorrect, yesterday I've found exactly that way, but for that it is need to use the following:
if X>=Y then
sin(X)>=sin(Y) but this isn't true in [0,Pi] interval.