10609 - Fractal

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:
Contact rotoZOOM

10609 - Fractal

Post by rotoZOOM »

My AC program (in online contest) got WA here.
What's problem?
Top
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

10609 WA

Post by angga888 »

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. :wink:

Regards,

Anggakusuma
Top
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Contact UFP2161

Post by UFP2161 »

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
Top
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Contact Larry

Post by Larry »

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
Top
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

10609

Post by angga888 »

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. :x

Now I get AC. :wink:

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


Regards,

Anggakusuma
Top
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Contact UFP2161

Post by UFP2161 »

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.
Top
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

10609

Post by angga888 »

Yes, I see.
Thanks :wink:


Anggakusuma
Top
windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: 10609

Post by windows2k »

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? :o
Thx
Top
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Contact UFP2161

Post by UFP2161 »

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.
Top
lobow
New poster
Posts: 10
Joined: Tue Jun 08, 2004 7:27 pm
Location: Pelotas - RS - Brazil
Contact:
Contact lobow

Post by lobow »

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

Tks
Top
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 »

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 :wink:


Anggakusuma
Top
lobow
New poster
Posts: 10
Joined: Tue Jun 08, 2004 7:27 pm
Location: Pelotas - RS - Brazil
Contact:
Contact lobow

Post by lobow »

How do you rotate de coordinates? I never heard of it.
Top
lobow
New poster
Posts: 10
Joined: Tue Jun 08, 2004 7:27 pm
Location: Pelotas - RS - Brazil
Contact:
Contact lobow

Post by lobow »

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?
Top
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 »

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. :wink:


Anggakusuma
Top
lobow
New poster
Posts: 10
Joined: Tue Jun 08, 2004 7:27 pm
Location: Pelotas - RS - Brazil
Contact:
Contact lobow

Post by lobow »

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
Top
Post Reply

Return to “Volume 106 (10600-10699)”