11122 - Tri Tri

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

Moderator: Board moderators

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

11122 - Tri Tri

Post by fpavetic » 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

rcrezende
New poster
Posts: 7
Joined: Mon Nov 28, 2005 4:53 am

Post by rcrezende » Sat Oct 14, 2006 7:09 pm

Your output is wrong!

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

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » 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?
Last edited by david on Sat Oct 14, 2006 7:52 pm, edited 1 time in total.

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

Post by fpavetic » 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?

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » 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 answer to
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)!

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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.

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

Re: 11122 - Tri Tri

Post by kalinov » 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

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » 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!

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » 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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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 :(

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sun Oct 15, 2006 11:19 am

My program passes all those cases, but I keep getting WA. Can anyone supply more tricky examples?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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!

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » 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.

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

Post by kalinov » 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! :)

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » 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

Post Reply

Return to “Volume 111 (11100-11199)”