Discussion of Problem 1312. TrayHere it is my code: #include <stdio.h> #include <math.h> #define eps 1e-16 struct plate { int id; double r, x, y; } p[3], pp[3], tp; double h, w, temp; double sq(double a) { return a*a;} int possible(); void output(int k); int main() { int i, j, k; scanf("%lf%lf%lf%lf%lf", &w, &h, &pp[0].r, &pp[1].r, &pp[2].r); pp[0].id = 0; pp[1].id = 1; pp[2].id = 2; for (i = 0; i < 3; ++i) for (j = 0; j < 3; ++j) for (k = 0; k < 3; ++k) if (i != j && i != k && j != k) { p[0] = pp[i]; p[1] = pp[j]; p[2] = pp[k]; if (possible()) { output(0); return 0; } } printf("0"); return 0; } //////////////////////////////////////////////////////////////// int possible() { p[0].x = p[0].r; p[0].y = p[0].r; p[1].x = w - p[1].r; p[1].y = p[1].r; if (sq(p[0].x - p[1].x) + sq(p[0].y - p[1].y) - sq(p[0].r + p[1].r) < -eps) { p[1].y = p[0].y + sqrt(sq(p[0].r + p[1].r) - sq(p[1].x - p[0].x)); if (p[1].y + p[1].r - h > eps) return 0; } p[2].x = p[2].r; p[2].y = h - p[2].r;
if (sq(p[0].x - p[2].x) + sq(p[0].y - p[2].y) - sq(p[0].r + p[2].r) < -eps) { p[2].x = p[0].x + sqrt(sq(p[0].r + p[2].r) - sq(p[2].y - p[0].y)); if (p[2].x + p[2].r - w > eps) return 0; }
if (sq(p[1].x - p[2].x) + sq(p[1].y - p[2].y) - sq(p[1].r + p[2].r) < -eps) return 0;
return 1; } void output(int k) { if (k == 1) { double t; for (k = 0; k < 3; ++k) { t = p[k].x; p[k].x = p[k].y; p[k].y = t; } } int i, j;
for (i = 0; i < 3; ++i) for (j = i+1; j < 3; ++j) if (p[i].id > p[j].id) { tp = p[i]; p[i] = p[j]; p[j] = tp; }
for (k = 0; k < 3; ++k) printf("%.4lf %.4lf ", p[k].x, p[k].y); } It seems to me, that right solution is much more complex :(! Is it forbidden to post WRONG programs here? Anyways my idea is : If there exists a solution then there exists a solution where two circles are in the corners of the rectangle. It is obvious because there is always the rightmost and the leftmost circle and we can drag them all the way to the corner. So what I do is: I take every pair of circles, try to put each of them in every corner (16 variants for a pair of circles). Then I "erase" all the area, where the center of the 3rd circle can not be located. Firstly, the last circle (I mean it's center) has to be located inside a rectangle (W-2R)x(H-2R) whre R - is the radius. We also must exclude two circles with radii R1+R and R2+R where R1 and R2 are the radii of the already existing circles. I store all the intersections of the 2 circles with the 4 lines (sides of the rectangle) and check all these points if they are possible positions for the last circle's center. Please tell me where am I wrong, or give me some critical test data. Thanks in advance. alex[LSD], a dumb russian programmer. The correct algo is much more complicated, and I don't want to explain it here - everyone who wants to solve this problem should manage it himself. First try my favorite test (I am not sure your program fails on it, I just like this test): 1000000 1000000 250001 250001 278000 There IS a solution :) Thanks, your test was really helpful. The algo is wrong, but not completely. My assumption about 2 corners was wrong, but the idea with rectangle and circles was pretty good. It just needed a recursive approach. I was amased that your original algorithm was exactly the same as me and I also got WA on test 3! I also failed in the testdata 1000000 1000000 250001 250001 278000! Amazing! Now I get AC and I want to say something. You said there are two "corner-center" points on the rectangle.The fact is that there is only one!!! (I can prove , but not very strict with one part,though it seems obvious) 1000000 1000000 250001 250001 278000 is just the counterexample of "two points". Use only one corner and then deal with two groups of intersections,you will get it!! 1000000 1000000 250001 250001 278000 work, but 3 WA, give something interesting tests, please Previouce people sad that AC algorithm much more complicated. But really AC algorithm much more simple, pure geometric and without otimization. One circle in corner and others have two opportunities: to be in another corner or to be adjacent to first circle and one of the sides of rectangle. Thus their centers determined. After we make verification:compare distance between centers and value R2+R3-eps. If first value greater than second- OK. This is only verification wich made with eps. Other verifications of placement should better make in __int64. Edited by author 13.09.2007 12:27 To svr. I've got AC with doubles and my default precision of 1e-8. No int64 at all. To all: I had WA3 because of wrong code for circle removal (it remained marked as used). Try to shuffle numbers in the first test and see if something strange happens or not. My solution is a full search! We should find all places for every plate: between two plates, plate & wall, 2 walls!!! Edited by author 04.09.2005 15:17 Edited by author 04.09.2005 15:17 Edited by author 05.09.2005 21:11 It is problem with rounding. When I changed in my program "write(x: 0: 5)" into "write(x: 0: 10)", I got AC. Hope, it will help you. Please, delete your code, others can profit by it. Thank you very much! Now I got AC! Thank you, Kit! You're super cool code analyser! Thank you! I've deleted my code, as you had advised! :) Set one circle in the up right corner, other in the down left corner, and third set where I can (after setting first two). Thanks. I think my pure-geometry based solution is correct, and I can not imagine test which it fails on, but it received WA(18). So I used some brute force optimizations and got AC, but I still don't know why was my first solution wrong... My AC prorgram uses only geometrical ideas. I think you just miss some special case. |
|