Page 1 of 2

10979 - How Many Triangles?

Posted: Thu Dec 29, 2005 4:38 pm
by Adrian Kuegel
Can someone give me some tricky test cases please? I always get WA with my program, but I was very careful to avoid any precision error and used only integer calculations.
Here are my own test cases:

Code: Select all

8
0 0 5 0
6 0 10 0
6 0 5 0
0 5 5 0
0 0 0 5
0 6 0 10
0 7 0 5
0 6 6 0

6
0 0 1 0
2 0 4 0
0 0 0 2
0 2 2 0
-10 1 10 1
0 1 3 1

3
-100 -100 100 100
-100 -99 100 99
100 -100 -100 99
My output is:
2
1
1

Posted: Thu Dec 29, 2005 5:29 pm
by tywok
Your output is OK. I used double and had no problem with it. Try these cases

Code: Select all

10
6 12 -19 -5
14 9 -23 -23
7 9 -10 -10
6 12 -6 -16
20 7 -12 -21
16 -9 -7 18
17 -7 -6 21
23 -20 -12 11
16 -23 -14 17
12 -24 -20 19

10
8 16 -7 -18
18 9 -6 -16
18 13 -12 -9
7 22 -22 -24
8 6 -14 -23
21 -20 -15 7
13 -11 -5 7
9 -13 -11 10
15 -14 -15 15
11 -6 -18 13

10
14 8 -9 -19
21 5 -11 -21
16 13 -9 -24
11 8 -22 -23
23 7 -14 -6
18 -20 -24 23
9 -15 -22 11
18 -11 -6 10
9 -17 -15 14
22 -18 -22 17

10
11 15 -6 -21
20 12 -20 -19
16 17 -15 -15
6 9 -11 -15
12 16 -12 -22
22 -12 -18 8
10 -14 -14 23
6 -13 -7 11
11 -15 -18 13
5 -16 -7 20

10
15 24 -9 -22
13 8 -20 -6
7 15 -16 -21
19 5 -21 -6
13 24 -13 -9
6 -19 -18 24
23 -23 -5 13
12 -12 -13 18
13 -8 -12 6
15 -22 -18 19

10
14 21 -20 -16
5 14 -24 -21
23 8 -9 -13
9 14 -14 -7
20 10 -18 -8
8 -12 -19 8
13 -5 -23 23
5 -21 -23 6
14 -23 -14 22
17 -7 -23 17

10
23 24 -15 -22
23 16 -20 -13
21 16 -7 -19
17 20 -13 -11
7 11 -20 -18
14 -7 -9 21
6 -23 -7 16
6 -24 -22 21
17 -14 -20 17
5 -15 -8 14

10
6 13 -6 -14
20 8 -7 -10
7 10 -13 -11
22 22 -17 -17
14 19 -6 -14
21 -14 -13 17
10 -20 -19 14
6 -17 -10 5
23 -18 -24 8
24 -21 -12 14

10
14 22 -11 -14
18 20 -22 -21
11 10 -13 -7
20 19 -19 -6
21 16 -11 -8
18 -20 -10 18
17 -13 -17 10
18 -21 -6 23
11 -7 -6 9
21 -7 -14 6

10
20 15 -18 -11
9 24 -17 -24
18 9 -19 -15
10 14 -11 -18
19 7 -13 -23
12 -10 -23 16
7 -10 -22 19
19 -9 -19 19
17 -24 -18 15
12 -22 -23 22

My AC program outputs this

Code: Select all

25
36
47
82
64
55
41
53
90
54

This test cases are not tricky, just random generated. I suposse the only tricky cases you can get is that a triangle has an edge like

Code: Select all

x----x-----x
where the two parts of the edge come from different edges of the input. Look at the clarification forum, there is a post that explains that.

I hope it helps! Viel Gluck! :wink:

Posted: Thu Dec 29, 2005 5:29 pm
by kalinov
Not very tricky, but try these:

Code: Select all

input:
4
1 1 3 3
2 1 2 3
3 1 1 3
1 2 3 2

6
1 1 3 3
2 1 2 3
3 1 1 3
1 2 3 2
1 3 2 3
2 3 3 3

4
1 1 4 4
3 3 6 6
5 6 5 1
1 2 6 2

4
1 6 4 3
3 4 6 1
5 1 5 6
1 5 6 5


output:
0
3
1
1

Posted: Thu Dec 29, 2005 5:39 pm
by Adrian Kuegel
Thank you :)
I had a mistake with a sign in the equation where I checked, if two line segments overlap.

Posted: Sat Dec 31, 2005 3:17 am
by Emilio
Hello there!
I'm getting WA but get correct output for all the sample input in this board and a lot of made by hand.
Are there any tricky cases?
My approach is make a set with all the points of the input segments and all the points of the segment intersection of all the input segments, then make all possible set of three points and check if the three segments maked with the three points can be maked from the initial input segments, I use double. To anyone that use double, what is your margin of error?
I have made two different codes and obtain the same results, help please!
Any good link to any site about geometry algorithm(in particular segments) will be appreciated!

Posted: Sat Dec 31, 2005 6:23 am
by polone
when you make every three points set you have to check if they are one the same line(lines in input)

Posted: Sat Dec 31, 2005 9:00 am
by Emilio
Yeah, I also check if they are colinear.

Posted: Sat Dec 31, 2005 9:16 am
by Andrey Grigorov
Hello there!
I'm getting WA but get correct output for all the sample input in this board and a lot of made by hand.
Are there any tricky cases?
Try this input:
6
1 0 3 0
2 0 4 0
1 0 3 2
3 2 2 0
3 0 3 2
3 2 4 0

Output:
6

Posted: Sat Dec 31, 2005 3:51 pm
by tywok
How do you check if they are colinear? There are a lot of cases that you should consider depending of each method. Suerte!

Posted: Sat Dec 31, 2005 3:58 pm
by tywok
i created 1000 tests cases with the same program that i used in the cases posted before. I uploaded them here
http://www.badongo.com/file.php?file=Te ... _10979.zip

Posted: Sun Jan 01, 2006 6:05 am
by Emilio
I get the correct output for all the cases of this board, and for your (tywok) 1000 test cases too.
I think that maybe is a precision error.
Thanks to all anyway but I'm desperate!
Any special case?

Posted: Mon Jan 02, 2006 1:28 am
by tywok
try this case..

Code: Select all

9
0 0 1 1
1 1 2 2
2 2 3 3
0 0 1 0
1 0 2 0
2 0 3 0
3 0 3 1
3 1 3 2
3 2 3 3
Output is 1. If it doesnt work my tip is to rewrite the solution, you may catch something wrong

Posted: Mon Jan 02, 2006 3:53 am
by Emilio
Thanks tywok!
I also get the correct output for your last case.
I clearly think is a precision error.
I'll try later another time. :(

Posted: Mon Jan 02, 2006 11:04 am
by Observer
Hi,

I don't think the test cases are that sensitive to precision errors. I have checked it with EPS ranging from 1e-2 to 1e-10, all giving the same (correct) result.

Posted: Tue Jan 03, 2006 2:01 am
by Emilio
Then a precision error musn't be my error, but I thought so because I obtain correct output for all the cases of this post and for the 1000 tywok test cases, I don't encounter the wretched boundary case :(