OJ Board

Posted: **Wed Jan 28, 2004 6:54 pm**

My AC program (in online contest) got WA here.
What's problem?

Posted: **Wed May 26, 2004 8:05 pm**

Hi,

I use recursion and always get WA in this problem. I get confused with this problem statement :

Each of the S lines after that contains two floating-point numbers indicating the coordinate of one terminal point or vertex. The terminal points should be sorted in increasing order of the value of abscissa of the coordinate. In case of a tie the points should be sorted in ascending order of the ordinate.

This means that the terminal points should be sorted, but how about the vertexs?

For input :

-300 -100 300 -200 25
-100 200 -100 -23.999 24.99
10 10 10 11 1
10 10 10 10.999999 1
12 10 10 10 1
10 10 10 12 1
-10000 -99 999 -1500 1000
5 5 -5 -8 .9

My output :

Case 1:
47
-300.00000 -100.00000
-191.26804 32.07929
-190.01202 -18.19714
-177.93069 -3.52167
-171.26202 -21.32214
-157.92468 -56.92309
-155.02405 76.10572
-153.76804 25.82929
-150.00000 -125.00000
-141.68671 40.50476
-133.76202 -27.57214
-118.78006 120.13214
-117.52405 69.85572
-115.01202 -30.69714
-105.44272 84.53119
-101.67468 -66.29809
-81.28006 113.88214
-69.19873 128.55762
-62.53006 110.75714
-49.19272 75.15619
-42.52405 57.35572
-25.03006 104.50714
-5.02405 51.10572
43.30127 109.80762
69.97595 38.60572
106.21994 82.63214
107.47595 32.35572
119.55728 47.03119
123.32532 -103.79809
143.71994 76.38214
147.48798 -74.44714
150.00000 -175.00000
155.80127 91.05762
162.46994 73.25714
166.23798 -77.57214
175.80728 37.65619
179.57532 -113.17309
182.47595 19.85572
195.81329 -15.74524
199.96994 67.00714
202.48196 -33.54571
203.73798 -83.82214
215.81931 -69.14667
219.97595 13.60572
222.48798 -86.94714
239.98196 -39.79571
300.00000 -200.00000
Case 2:
23
-100.00000 -23.99900
-100.00000 32.00075
-100.00000 144.00025
-100.00000 200.00000
-75.75140 46.00069
-75.75140 130.00031
-63.62710 11.00084
-63.62710 39.00072
-63.62710 137.00028
-63.62710 165.00016
-51.50279 46.00069
-51.50279 130.00031
-39.37849 25.00078
-39.37849 151.00022
-27.25419 18.00081
-27.25419 32.00075
-27.25419 60.00062
-27.25419 74.00056
-27.25419 102.00044
-27.25419 116.00037
-27.25419 144.00025
-27.25419 158.00019
-3.00559 88.00050
Case 3:
2
10.00000 10.00000
10.00000 11.00000
Case 4:
2
10.00000 10.00000
10.00000 11.00000
Case 5:
5
10.00000 10.00000
10.50000 10.00000
11.00000 9.13397
11.50000 10.00000
12.00000 10.00000
Case 6:
5
9.13397 11.00000
10.00000 10.00000
10.00000 10.50000
10.00000 11.50000
10.00000 12.00000
Case 7:
23
-10000.00000 -99.00000
-8053.91220 1468.10877
-7482.69940 3210.34253
-7250.25000 -449.25000
-7214.81200 2571.22294
-6795.26190 3122.78003
-6679.03720 1292.98377
-6411.14980 653.86418
-5956.16170 4225.89421
-5420.38690 2947.65503
-4732.94940 2860.09253
-3893.84920 3963.20671
-3358.07440 2684.96753
-2670.63690 2597.40503
-2286.52480 128.48918
-1866.97470 680.04627
-1831.53670 3700.51921
-1750.75000 -1149.75000
-1295.76190 2422.28003
-1027.87450 1783.16044
-608.32440 2334.71753
-492.09970 504.92127
999.00000 -1500.00000

Is my output correct?

Thank's for any help.

Regards,

Anggakusuma

Posted: **Wed May 26, 2004 9:05 pm**

I got slightly different outputs with my AC code:

The diff file first:

$ diff outAC outWA

61a62,63
> -51.50279 46.00069
> -51.50279 130.00031
66c68
< -27.25419 60.00063
---
> -27.25419 60.00062
72d73
< -3.00559 46.00069
74d74
< -3.00559 130.00031
80c80,82
< 0
---
> 2
> 10.00000 10.00000
> 10.00000 11.00000

The entire output file:

Case 1:
47
-300.00000 -100.00000
-191.26804 32.07929
-190.01202 -18.19714
-177.93069 -3.52167
-171.26202 -21.32214
-157.92468 -56.92309
-155.02405 76.10572
-153.76804 25.82929
-150.00000 -125.00000
-141.68671 40.50476
-133.76202 -27.57214
-118.78006 120.13214
-117.52405 69.85572
-115.01202 -30.69714
-105.44272 84.53119
-101.67468 -66.29809
-81.28006 113.88214
-69.19873 128.55762
-62.53006 110.75714
-49.19272 75.15619
-42.52405 57.35572
-25.03006 104.50714
-5.02405 51.10572
43.30127 109.80762
69.97595 38.60572
106.21994 82.63214
107.47595 32.35572
119.55728 47.03119
123.32532 -103.79809
143.71994 76.38214
147.48798 -74.44714
150.00000 -175.00000
155.80127 91.05762
162.46994 73.25714
166.23798 -77.57214
175.80728 37.65619
179.57532 -113.17309
182.47595 19.85572
195.81329 -15.74524
199.96994 67.00714
202.48196 -33.54571
203.73798 -83.82214
215.81931 -69.14667
219.97595 13.60572
222.48798 -86.94714
239.98196 -39.79571
300.00000 -200.00000
Case 2:
23
-100.00000 -23.99900
-100.00000 32.00075
-100.00000 144.00025
-100.00000 200.00000
-75.75140 46.00069
-75.75140 130.00031
-63.62710 11.00084
-63.62710 39.00072
-63.62710 137.00028
-63.62710 165.00016
-39.37849 25.00078
-39.37849 151.00022
-27.25419 18.00081
-27.25419 32.00075
-27.25419 60.00063
-27.25419 74.00056
-27.25419 102.00044
-27.25419 116.00037
-27.25419 144.00025
-27.25419 158.00019
-3.00559 46.00069
-3.00559 88.00050
-3.00559 130.00031
Case 3:
2
10.00000 10.00000
10.00000 11.00000
Case 4:
0
Case 5:
5
10.00000 10.00000
10.50000 10.00000
11.00000 9.13397
11.50000 10.00000
12.00000 10.00000
Case 6:
5
9.13397 11.00000
10.00000 10.00000
10.00000 10.50000
10.00000 11.50000
10.00000 12.00000
Case 7:
23
-10000.00000 -99.00000
-8053.91220 1468.10877
-7482.69940 3210.34253
-7250.25000 -449.25000
-7214.81200 2571.22294
-6795.26190 3122.78003
-6679.03720 1292.98377
-6411.14980 653.86418
-5956.16170 4225.89421
-5420.38690 2947.65503
-4732.94940 2860.09253
-3893.84920 3963.20671
-3358.07440 2684.96753
-2670.63690 2597.40503
-2286.52480 128.48918
-1866.97470 680.04627
-1831.53670 3700.51921
-1750.75000 -1149.75000
-1295.76190 2422.28003
-1027.87450 1783.16044
-608.32440 2334.71753
-492.09970 504.92127
999.00000 -1500.00000

Posted: **Wed May 26, 2004 9:08 pm**

For the second case, I get:

Code: Select all

Case 2:
23
-100.00000 -23.99900
-100.00000 32.00075
-100.00000 144.00025
-100.00000 200.00000
-75.75140 46.00069
-75.75140 130.00031
-63.62710 11.00084
-63.62710 39.00072
-63.62710 137.00028
-63.62710 165.00016
-39.37849 25.00078
-39.37849 151.00022
-27.25419 18.00081
-27.25419 32.00075
-27.25419 60.00062
-27.25419 74.00056
-27.25419 102.00044
-27.25419 116.00038
-27.25419 144.00025
-27.25419 158.00019
-3.00559 46.00069
-3.00559 88.00050
-3.00559 130.00031

Posted: **Thu May 27, 2004 8:26 am**

Wow... thanks for your reply.

I found my mistakes. I made two mistakes :
- I misplaced my if command, and
- I faced so many percision errors.

Now I get AC.

NB: but I still don't understand why the third and forth test case (input 3 & 4) produce different output.

Regards,

Anggakusuma

Posted: **Thu May 27, 2004 5:14 pm**

Well, the distance between (10,10) and (10,10.999999) is 0.999999 which is less than 1, so don't even get past the first part of the fractal, while in the other one, the initial distance is 1, so it's greater than or equal to the threshold length, so it is equal.

At least, that's how my program handled it.

Posted: **Fri May 28, 2004 4:56 am**

Yes, I see.
Thanks

Anggakusuma

Posted: **Fri May 28, 2004 9:38 am**

angga888 wrote:Yes, I see.

Sorry, I have a stupid question.
Like the input:
10 10 -10 -10 5.1
A(10,10) B(-10,-10)
We can find C(5,5) D(-5,-5)
How could we find E?
E maybe (8.66025,-8.66025) or (-8.66025,8.66025)
How can I decide E?

Thx

Posted: **Fri May 28, 2004 2:09 pm**

If you look at the sample image, if the input is A then B, you get C D and E as shown. However, if the input were reversed and given as B then A, you get D C and the the opposite value for E.

It doesn't specifically say what to do (at least I couldn't find any sentence that says it). It's just try one way, see if it matches the input, if not, then the other way is correct.

Posted: **Tue Jun 08, 2004 7:41 pm**

Hi! Im having problems to discover the points of the equilateral triangle. Someone can help me with how can I draw this triangle?

Tks

Posted: **Wed Jun 09, 2004 6:08 am**

Hi lobow,

I assume that the equilateral triangle always on the left side. I just try it and get the same result as the sample output. The problem description doesn't specify that. To get the points in an equilateral triangle, first I rotate the coordinates so that they become parallel to the x-axis or y-axis. After this, we can find all the points easilly. Next, I rotate them back again and get the real coordinates.

Hope it helps

Anggakusuma

Posted: **Wed Jun 09, 2004 3:29 pm**

How do you rotate de coordinates? I never heard of it.

Posted: **Thu Jun 10, 2004 12:37 am**

Another dumb question... When in the problem says to divide AB in ratio of 1:3, you divided it in 3 or 4 pieces? And if I use (point A + the distance of the piece) I can get the point C?

Posted: **Thu Jun 10, 2004 8:13 am**

lobow wrote:How do you rotate de coordinates? I never heard of it.

I use the following formula:
(x'-p)=(cos@ -sin@)(x-p)
(y'-q) (sin@ cos@)(y-q)
so:
x' = cos@ * (x-p) - sin@ * (y-q) + p
y' = sin@ * (x-p) + cos@ * (y-q) + q
Assumption:
x = x-coordinate of the point you want to rotate.
y = y-coordinate of the point you want to rotate.
@ = the angle.
p = x-coordinate of the rotation axis.
q = y-coordinate of the rotation axis.
x'= x-coordinate of the point after a rotation of @.
y'= y-coordinate of the point after a rotation of @.

lobow wrote:When in the problem says to divide AB in ratio of 1:3, you divided it in 3 or 4 pieces?

into 4 pieces.

Hope this helps you.

Anggakusuma

Posted: **Thu Jun 10, 2004 10:36 pm**

angga888 wrote: x' = cos@ * (x-p) - sin@ * (y-q) + p
y' = sin@ * (x-p) + cos@ * (y-q) + q

I used this formula like this, see if its right:

I have A and B points and want to know the C

used x and y as valors of A
p and q valors of the midpoint of AB
and cos and sin of 90

OJ Board

10609 - Fractal

10609 - Fractal

10609 WA

10609

10609

Re: 10609