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

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

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

Hello.
I think this problem is simple (if u know little geometry ), 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
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.