11281 - Triangular Pegs in Round Holes

[baodog]

right ... that approach is not quite correct... changed to different one,
but still compute minimum diameter.

[baodog]

btw, All numbers fit into double, and the correct EPS
should be 1e-6 or less. Hope this helps people still getting WA.

[Mushfiqur Rahman]

I got several times WA. Can anybody help?
I think my logic is correct.
My code passed the sample input and the inputs input which is given in the board.

Code: Select all

 Removed

[goodwill]

Code: Select all

theta = acos( ( a*a + b*b - c*c )/(2*a*b) ) ;
alpha = acos( a/D[j] ); // since D[j] = 2*r ; 

I believe that you have used the wrong angle.
I used this one

Code: Select all

theta = acos( ( a*a + b*b - c*c )/(2*a*b) ) ;
alpha = asin(c/D[j] );
if (alpha-theta>-eps) ...

And you used it for all 3 edges of the triangle.[/quote]

[Mushfiqur Rahman]

Goodwill wrote:

I believe that you have used the wrong angle.

thanks for your reply. But I thought a lot about my logic but yet not found any wrong. Can u give me some sample i/o so that i can justify my logic.

[goodwill]

i change your program to compute the condition for all 3 edges of the triangle and it got AC:

Code: Select all

bool valid(double a, double b, double c, double d){
     double theta, alpha, eta, xx;
     if( a - d > eps ) return false ;
              
     theta = acos( ( a*a + b*b - c*c )/(2*a*b) ) ;
            
     alpha = acos( a/d ); // since D[j] = 2*r ;
           
     eta = theta - alpha ;
            
     xx = d*cos(eta) ;
     return (xx-b>-eps);
}

And in the main, you call this:

Code: Select all

if (valid(a,b,c,D[j]) || valid(b,c,a,D[j]) || valid(c,a,b,D[j]))  ...

[Mushfiqur Rahman]

Thanks for your reply.

Obviously that was the problem.

I caught it after just sending my previous post.

[markthom]

I also get WA with the following block of code:

Code: Select all

#include <iostream>
#include <cmath>
using namespace std;

#define PI 3.141592653589793

int main()
{
	double holes[100];
	int num_holes = 0;
	int i;
	
	cin >> num_holes;
	
	for(i = 0; i < num_holes; i++) {
		cin >> holes[i];
	}
	
	int num_pegs = 0;
	
	cin >> num_pegs;
	
	char letters[27] = "ABCDEFGHIJKLMNOPQRSTUVXYZ";
	
	for(i = 0; i < num_pegs; i++)
	{
		double d1;
		double d2;
		double d3;
		
		bool fit_in_holes[100];
		bool does_fit = false;
		
		cin >> d1 >> d2 >> d3;
		
		for(int j = 0; j < num_holes; j++) 
		{
			double r = holes[j] / 2.0;
			if(2.0*r < d3) continue;
		
			double theta = acos(((2.0*r*r - d3*d3) / (2.0*r*r)));
			double delta = acos(((d2*d2 + d3*d3 - d1*d1) / (2.0 * d2 * d3)));
			double beta = delta - 0.5 * (PI - theta);
			
			if(2.0 * r * cos(beta) >= d2) {
				fit_in_holes[j] = true;
				does_fit = true;
			}
		}
				
		if(does_fit == true) {
			cout << "Peg " << letters[i] << " will fit into hole(s):";
		
			for(int k = 0; k < num_holes; k++) 
			{
				if(fit_in_holes[k] == true) {
					cout << " " << (k+1);
					fit_in_holes[k] = false;
				}
			}

			cout << endl;
		} else {
			cout << "Peg " << letters[i] << " will not fit into any holes" << endl;
		}
	}	
	
	return 0;
}

I think my method may be a little different from what the others have posted here, but I'm confident it should work.

Here's a quick run down of my algorithm:

1) Theta = Angle subtended by a chord of length d3 at the center of the circle
2) Delta = Angle formed by sides of lengths d3 and d2 in user-given triangle
3) Beta = Delta - (180 - Theta) / 2, since the triangle containing angle theta is isosceles.

At this point, beta is an angle of a new triangle, the hypotenuse of which is the diameter of the circle, since it passes through the circle center. This means that any triangle formed using this chord and a point on the circumference will be a right triangle.

Therefore, I take the maximum possible length of the side of the triangle opposing the hypotenuse. If the length of this side exceeds or equals d2, then the peg will fit the circle. Otherwise, it won't.

And that's it. I've tested it with the trickier bits of input posted on this thread, and it works correctly. I don't see what cases I might have missed.

[Saswat2603]

I need some critical test cases. My program passed all the test cases mentioned in this thread, yet gets a WA.

[hotienvu]

Hi, I got too many WAs for this problem, still cant figure out the bug yet. But I think my approach is correct. i.e. for every edge AB of the triangle, calculate the
opposite angle and if check it is greater than the obtuse angel formed by a point in a circle and arc AB.
My program passes all the test cases in the forum, i tried many others but those may not be the right one.

Code: Select all

#include <iostream>
#include <cmath>

using namespace std;

#define fo(i,j,k) for (i= j;i<k;i++)
#define rep(i,j,k) for (i=j;i<=k;i++)
#define fod(i,j,k) for(i=j;i>=k;i--)
#define MAXN  101
#define eps 1e-10

//FILE *fin = fopen ("pegs.in","r");
//FILE *fout = fopen ("pegs.out","w");

#define fin stdin
#define fout stdout


int N,M;
double r[MAXN];


bool ok (double a, double b, double c, double d){
     double t1,t2,t3;
     if(a - d > eps) return false;
     t1 = acos((b*b + c*c - a*a )/(2*c*b)) ;
     t2 = asin(a/d); 
     return (t1 - t2>=-eps);
}


int main () {
  fscanf (fin,"%d",&M);
  int i;
  fo(i,0,M) fscanf (fin,"%lf",&r[i]);
  
  fscanf (fin,"%d",&N);
  fo(i,0,N) {
    double a,b,c,c1,c2,c3;
    fscanf (fin, "%lf %lf %lf",&a,&b,&c);
    bool mark[M+1];
    memset (mark, false , sizeof (mark));
    bool found = false;
    int j;
    fo(j,0,M) {
      double t = r[j];
      if (ok (a,b,c,t)||ok(b,c,a,t)||ok(c,a,b,t)) {
        mark[j] = true;
        found = true;
      }
    }
    if (found) {
      fprintf (fout,"Peg %c will fit into hole(s): ",(char) 65+i);
      fo(j,0,M-1)
        if (mark[j]) fprintf (fout,"%d ",j+1);
      if(mark[j]) fprintf(fout,"%d",j+1);
    }
    else fprintf (fout,"Peg %c will not fit into any holes",(char) 65+i);
    if (i<N-1)fprintf (fout,"\n");

  }
  return 0;
}

[Shafaet_du]

minimum bounding circle==circumcircle if the triangle is not obtuse.
in case of obtuse circle the radii of minimum bounding circle==largest side of the triangle.

cosine of obtuse angle is negative.

why don't use long double for better precision??

Good luck.

[Imti]

I have solved this problem.
At my First attempt ,To decide whether triangle is obtuse or not I computed angle of traingle from sine law.
D=Diameter of circum-circle.
From sine law
A= arc sin(a/D)*180.0/PI(Here Capital letter A denotes angle, opposite of side denoted with a)
In this way I found three angle and checked whether any of them greater than 90 deg.But it was not giving right measurement, for obtuse angle.Like for following
1
100
1
51 51 100
After facing this I tried cosine law and checked "negative issue" then got it ACC..
But I want to know why sine law don't work here?Or maybe I'm misinterpreting?