10979 - How Many Triangles?

[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

[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!

[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

[Adrian Kuegel]

Thank you
I had a mistake with a sign in the equation where I checked, if two line segments overlap.

[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!

[polone]

when you make every three points set you have to check if they are one the same line(lines in input)

[Emilio]

Yeah, I also check if they are colinear.

[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

[tywok]

How do you check if they are colinear? There are a lot of cases that you should consider depending of each method. Suerte!

[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

[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?

[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

[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.

[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.

[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