P3498 - Stacking Cylinders (from North America 2006-06)

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

Post Reply
KvaLe
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm

P3498 - Stacking Cylinders (from North America 2006-06)

Post by KvaLe » Wed Jan 04, 2006 10:32 pm

Hello.
I think this problem is simple (if u know little geometry :wink: ), but it get's WA, than I saw in this problem's ranklist and nobody has solved it. Maybe there's some problem with judge system or something other. Here is my code and if u find bug post here plz:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>

using namespace std;

class point {
  public:
    double x, y;
    
    point (double X, double Y) { x = X, y = Y; }
    point () {}
    
    void scan () { scanf ("%llf", &x); y = 1; }
    
    void print () { printf ("%.4llf %.4llf\n", x, y); }
    
    point median (point p) { return point (0.5*(x+p.x), 0.5*(y+p.y)); }
    
    double dist (point p) { return sqrt ((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y)); }
};

class line {
  public:
    double a, b, c;
    
    line (double A, double B, double C) { a = A, b = B, c = C; }
    line (point p, point q) { a = q.y-p.y, b = p.x-q.x, c = a*p.x+b*p.y; }
    line () {}
    
    line per (point p) { return line (-b, a, -b*p.x+a*p.y); }
};

int n;
point p [10][10];

point solve_equation (double a1, double b1, double c1, double a2, double b2, double c2) {
  double det = a1*b2-a2*b1;
  return point ((c1*b2-c2*b1)/det, (a1*c2-a2*c1)/det);
}

point find_center (point p, point m, line l) {
  double d = p.dist (m);
  double s = d*sqrt (4-d*d);
  return solve_equation (l.a, l.b, l.c, p.y-m.y, m.x-p.x, s+(p.y-m.y)*m.x+(m.x-p.x)*m.y);
}

int main (void) {
  int i, j, k, t, T = 0;
  point m;
  line l;
  for (scanf ("%d", &t); t--; ) {
    scanf ("%d", &n);
    for (i = 0; i < n; i++) {
      p [0][i].scan ();
      for (j = i; j && p [0][j-1].x > p [0][j].x; j--) swap (p [0][j].x, p [0][j-1].x);
    }
    n--;
    for (k = 0; k < n; k++) {
      for (i = 0; i < n-k; i++) {
        m = p [k][i].median (p [k][i+1]);
        l = line (p [k][i], p [k][i+1]).per (m);
        p [k+1][i] = find_center (p [k][i], m, l);
      }
    }
    printf ("%d: ", ++T);
    p [n][0].print ();
  }
  exit (0);
}
Giorgi Lekveishvili

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Feb 09, 2006 8:56 am

Ok, that thing is interesting... I tried it in Java, it wouldn't work, so I got judge's input (after the practice!) and found out that there were a lot of precision errors. Hm, so I reimplement it in C. Same thing. I played with some EPS values, no luck.

So I go check judge's solution - and I try their way of finding centers exactly step by step (as in (d/2)*(d/2) instead of d*d/4, stuff like that). Nothing.

My compiler is:
gcc version 3.4.3 20041212 (Red Hat 3.4.3-9.EL4)

Here's my rather clumsy C implementation (I am new to C):

Code: Select all

#include <stdio.h>
#include <math.h>

void findCenter(double x0, double y0, double x1, double y1, double * res){
	double d, t;
	d = sqrt((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1));
	t = sqrt(16.0-d*d)/d;
	res[0] = 0.5*(x0+x1-t*(y1-y0));
	res[1] = 0.5*(y0+y1+t*(x1-x0));
}
int main() {
	int nc, n, i, j, k;
	double res[2];
	double xs[11][11];
	double ys[11][11];
	scanf("%d", &nc);
	for(k=1;k<=nc;k++){
		printf("%d: ",k);
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%lf", &xs[0][i]);
			ys[0][i] = 1.0;
		}
		for (i = 1; i < n; i++) {
			for (j = 0; j < n - i; j++) {
				findCenter(xs[i-1][j], ys[i-1][j], xs[i-1][j+1], ys[i-1][j+1], res);
				xs[i][j] = res[0];
				ys[i][j] = res[1];
			}
		}
		printf("%.4lf %.4lf\n", xs[n-1][0], ys[n-1][0]);
	}
	return 0;
}

Maybe someone can point out what I am doing wrong (Java code has the same idea)

Darko

P.S. I just tried that c++ code above and got some really weird output.

Post Reply

Return to “ACM ICPC Archive Board”