11122 - Tri Tri

[fpavetic]

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]

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]

Shouldn't the answer to case 9:

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

be no?

[fpavetic]

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]

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

[little joey]

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]

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]

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]

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.

[little joey]

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]

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

[little joey]

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]

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]

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]

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