Page 1 of 2

### 11122 - Tri Tri

Posted: Sat Oct 14, 2006 6:13 pm
can anybody provide some tricky cases for this task? thanks

some io:

Code: Select all

``````11

0 0 2 0 0 2
1 1 3 3 2 3

0 0 2 0 0 2
3 0 5 0 4 2

0 0 1 0 1 1
0 0 1 0 1 1

0 0 0 1 1 0
0 0 3 1 1 3

0 0 100 0 0 100
1 1 3 1 1 3

1 1 3 1 1 3
0 0 100 0 0 100

0 0 2 0 0 2
0 0 1 0 0 1

0 0 1 0 0 1
0 0 2 0 0 2

0 0 0 1 1 0
0 1 1 0 1 1

0 0 1 0 0 1
0 0 -1 0 0 -1

0 0 1 0 0 1
0 0 1 0 0 -1

``````

my output:

Code: Select all

``````pair 1: no
pair 2: no
pair 3: yes
pair 4: yes
pair 5: yes
pair 6: yes
pair 7: yes
pair 8: yes
pair 9: no
pair 10: no
pair 11: no
``````
thanks

Posted: Sat Oct 14, 2006 7:09 pm

Code: Select all

``````11

0 0 2 0 0 2
1 1 3 3 2 3

0 0 2 0 0 2
3 0 5 0 4 2

0 0 1 0 1 1
0 0 1 0 1 1

0 0 0 1 1 0
0 0 3 1 1 3

0 0 100 0 0 100
1 1 3 1 1 3

1 1 3 1 1 3
0 0 100 0 0 100

0 0 2 0 0 2
0 0 1 0 0 1

0 0 1 0 0 1
0 0 2 0 0 2

0 0 0 1 1 0
0 1 1 0 1 1

0 0 1 0 0 1
0 0 -1 0 0 -1

0 0 1 0 0 1
0 0 1 0 0 -1

``````
Accpted:

Code: Select all

``````pair 1: no
pair 2: no
pair 3: yes
pair 4: yes
pair 5: yes
pair 6: yes
pair 7: yes
pair 8: yes
pair 9: yes
pair 10: no
pair 11: no
``````

Posted: Sat Oct 14, 2006 7:23 pm
Shouldn't the answer to case 9:

0 0 0 1 1 0
0 1 1 0 1 1

be no?

Posted: Sat Oct 14, 2006 7:40 pm
i think that output for tc9 should be no, because the only points these two triangles share are on the edge they share, and according to the problem statement, points on edges are not interior. or have i misunderstood something?

Posted: Sat Oct 14, 2006 8:13 pm
According to the problem description:
No points on the edges or vertices are considered interior to a triangle.
the test case 9 is clearly "no"!
I hope that the problem setter (Mr. Hossain) or his "mentor" Mr. Wulff
will be kind enough to explain their way of thinking (or expressing
themselves)!

Posted: Sat Oct 14, 2006 8:52 pm
The fact that an accepted solution prints a wrong answer for a specific input, doesn't necessarily imply that the judges' data is wrong, it just indicates that it is probably too weak to catch all user-mistakes. The answer to case 9 is indeed 'no', and in fact all of rcrezende's output is correct.

Further: I'm not Mr. Hossain's mentor, I merely wrote an alternative solution to his problem (at which occasion I mentioned that it would be preferable to add 1000 or so more testcases, just to eliminate faulty solutions as seen above. I guess there was not enough time for that anymore).

Does the second half of your question ask me to explain why I think the way do and why I express myself the way I do? I'm sorry, I can't. I don't understand that myself.

### Re: 11122 - Tri Tri

Posted: Sat Oct 14, 2006 9:12 pm
fpavetic wrote:can anybody provide some tricky cases for this task? thanks
This one was tricky for me:

Code: Select all

``````input:
1

0 0 5 0 2 4
4 0 5 0 -4 16

output:
pair 1: yes``````

Posted: Sat Oct 14, 2006 9:50 pm
Thanks kalinov for the excellent case!
I saw my mistake! (I even begin to understand why the wrong solution
was accepted )
Please accept my apologies little joey! But after having your brain in an
"endless loop" for 5+ hours and after reading the previous messages in
this thread you get a bit aggressive, shouldn't you ? Sorry again!

### hmm

Posted: Sat Oct 14, 2006 11:30 pm
little joey wrote: Further: I'm not Mr. Hossain's mentor, I merely wrote an alternative solution to his problem (at which occasion I mentioned that it would be preferable to add 1000 or so more testcases, just to eliminate faulty solutions as seen above. I guess there was not enough time for that anymore).
The problem setter was ill so testcase could not be added. Sorry! I came to know just before the contest that he was sick.

Posted: Sun Oct 15, 2006 12:00 am
Wish him all the best. Maybe he can add more testcases later to the UVA data.

BTW. These trapeziums are killing me... just when I thought I knew all your tricks

Posted: Sun Oct 15, 2006 11:19 am
My program passes all those cases, but I keep getting WA. Can anyone supply more tricky examples?

Posted: Sun Oct 15, 2006 1:54 pm
david wrote:My program passes all those cases, but I keep getting WA. Can anyone supply more tricky examples?
Why let others do the work for you?
Take your scetch-book and pencil and make some of your own. It's not so hard finding the tricky cases (co-linearity, nearly touching, shared corners, paralel to the axis, etc. etc.), and the nice thing is: you can instantly check them by inspecting your scetch.

Finding the tricky cases in a programming assignment is as much of a necessary skill for a programmer as making the actual code. So don't waste the opportunity to get some practice in that department!

Posted: Sun Oct 15, 2006 1:58 pm

Why let others do the work for you?
Take your scetch-book and pencil and make some of your own. It's not so hard finding the tricky cases (co-linearity, nearly touching, shared corners, paralel to the axis, etc. etc.), and the nice thing is: you can instantly check them by inspecting your scetch.
And what makes you think I haven't done just that before?
If I ask, it's precisely because I have. Moreover, I spent 4 hours during the contest trying to figure out what's wrong, and afterwards I also tried a lot of cases by hand. I wouldn't post in the forum otherwise. So don't tell me that.

Posted: Sun Oct 15, 2006 2:34 pm
david wrote:My program passes all those cases, but I keep getting WA. Can anyone supply more tricky examples?
Make sure you don't overflow if you use integer arithmetics. And if you use floating point numbers make sure you make your comparisons are good (use epsilon).

Good luck!

Posted: Sun Oct 15, 2006 2:53 pm
Make sure you don't overflow if you use integer arithmetics. And if you use floating point numbers make sure you make your comparisons are good (use epsilon).
Thanks for replying, but I use long long and I checked with assert that all input data fit within an int, so multiplications won't overflow and that shouldn't be a problem.
My method is as follows. I return "yes" whenever one of the following situations occurs:
1. One of the vertices of a triangle is strictly inside the other
2. Two of the sides of the triangles intersect properly.
3. One of the triangles (say ABC) has two vertices (A and B) within a side DE of the other triangle DEF, and DEC and DEF have the same orientation.
Is there anything I overlooked?
Anyway here's my code, in case someone wants to test it (I'm pretty sure the geometric functions are correct, so the problem must be elsewhere).

Code: Select all

``````#include <algorithm>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;

typedef long long tipo;
#define error 0

struct punto {
tipo x, y;
punto(tipo a = 0, tipo b = 0) : x(a), y(b) {}
bool operator==(punto &c) { return x == c.x && y == c.y; }
bool operator!=(punto &c) { return !(*this == c); }
};
typedef pair<punto, punto> segm;

punto operator-(punto a, punto b) {
return punto(a.x - b.x, a.y - b.y);
}

/* Coordenada z del producto vectorial */
tipo operator^(punto a, punto b) {
return a.x * b.y - a.y * b.x;
}

/* Devuelve 1 si el punto b est``````