11123 - Counting Trapizoid

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

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

11123 - Counting Trapizoid

Post by Adrian Kuegel »

After checking my program against a brute force program I still haven't found a test case where the answers differ. Can someone please confirm following input for me, so that I know if my brute force program is correct?

Code: Select all

100
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
4 0
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
5 0
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
5 9
6 0
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
8 0
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
8 9
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
0
My output is:
Case 1: 269760

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

Hmm

Post by shahriar_manzoor »

Yes matches with judge solutions.

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

Post by little joey »

Well, it doesn't. I just got accepted with a solution that just prints the answer, without the case-number. So printf("%d\n",count) in stead of printf("Case %d: %d\n",caseno,count).

Please Shahriar, that is too tricky for most of us...

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

hmm

Post by shahriar_manzoor »

deleted
Last edited by shahriar_manzoor on Tue Oct 17, 2006 6:20 am, edited 1 time in total.

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay »

will the brute force approach do here...???
If I will myself do hashing, then who will do coding !!!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

I used to have O(n^2 log n + m^2 log m) that TLE where m is the number of distinct slopes.

Now, I have O(n^2 log n + m) that AC, but now m is the number of pairs of equal slopes.

My second solution seems to be much faster for the testcases.
Last edited by sclo on Mon Oct 16, 2006 8:47 am, edited 1 time in total.

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay »

i m really poor in geometry...

any hints of how to approach this problem???
If I will myself do hashing, then who will do coding !!!

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny »

any hints of how to approach this problem???
i solved it like this:


1. calculate the slopes of all possible n*(n-1)/2 lines
2. sort the lines by slopes
3. now check the pairs of parallel lines i mean lines with equal slopes. if parallel
then check whether the two lines formed by the endpoints of the 1st
& 2nd line are parallel or not.

suppose, AB & CD are parallel. then check wheter AC , BD && AD,BC
are parallel.

if not, definitely the shape is a Trapizoid.

my complexity in worst case is : O(n^2 + mlogm + m^2)
where m is the number of lines. the worst case occurs if all vertices are co-linear.
Last edited by sunny on Thu Oct 19, 2006 12:47 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

My algorithm is same as sunny's. But I m getting wa. Here is the code

Code: Select all

Accepted :)
Can anyone help me? Thanks in advance.
Last edited by Jan on Tue Oct 17, 2006 6:54 am, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

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

hmm

Post by shahriar_manzoor »

Now the judge data is according to problem statement, so you have to print "Case " also

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Thanks. Got Accepted.
Ami ekhono shopno dekhi...
HomePage

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

Clarification: Can I simply assume that all the input points are distinct?
I code, therefore I am.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

There are no duplicate points or else my program will give RE for that.
Last edited by sclo on Thu Oct 19, 2006 10:13 am, edited 1 time in total.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

Hmm.. your answer is a little confusing to me...
So there could be duplicated points, right?
If so, what should be the output of this case?

Code: Select all

5
0 0
0 0
1 0
1 1
0 2
0
1? or 2?
I code, therefore I am.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

There are no duplicate points.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 111 (11100-11199)”