10979 - How Many Triangles?

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

Moderator: Board moderators

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

10979 - How Many Triangles?

Post by Adrian Kuegel » Thu Dec 29, 2005 4:38 pm

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
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Thu Dec 29, 2005 5:29 pm

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:
Impossible is nothing

kalinov
New poster
Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia

Post by kalinov » Thu Dec 29, 2005 5:29 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Dec 29, 2005 5:39 pm

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

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sat Dec 31, 2005 3:17 am

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
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Sat Dec 31, 2005 6:23 am

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

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sat Dec 31, 2005 9:00 am

Yeah, I also check if they are colinear.

Andrey Grigorov
New poster
Posts: 8
Joined: Thu Jul 15, 2004 3:52 pm
Location: Russia, Cherepovets

Post by Andrey Grigorov » Sat Dec 31, 2005 9:16 am

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
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Sat Dec 31, 2005 3:51 pm

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

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Sat Dec 31, 2005 3:58 pm

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
Impossible is nothing

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sun Jan 01, 2006 6:05 am

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
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Mon Jan 02, 2006 1:28 am

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
Impossible is nothing

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Mon Jan 02, 2006 3:53 am

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Mon Jan 02, 2006 11:04 am

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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Tue Jan 03, 2006 2:01 am

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

Post Reply

Return to “Volume 109 (10900-10999)”