Page 1 of 2
11123 - Counting Trapizoid
Posted: Sun Oct 15, 2006 1:40 am
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
Hmm
Posted: Sun Oct 15, 2006 2:20 am
by shahriar_manzoor
Yes matches with judge solutions.
Posted: Sun Oct 15, 2006 2:26 am
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...
hmm
Posted: Sun Oct 15, 2006 2:32 am
by shahriar_manzoor
deleted
Posted: Sun Oct 15, 2006 3:37 pm
by vinay
will the brute force approach do here...???
Posted: Sun Oct 15, 2006 5:56 pm
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.
Posted: Sun Oct 15, 2006 7:34 pm
by vinay
i m really poor in geometry...
any hints of how to approach this problem???
Posted: Sun Oct 15, 2006 8:24 pm
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.
Posted: Tue Oct 17, 2006 5:57 am
by Jan
My algorithm is same as sunny's. But I m getting wa. Here is the code
Can anyone help me? Thanks in advance.
hmm
Posted: Tue Oct 17, 2006 6:22 am
by shahriar_manzoor
Now the judge data is according to problem statement, so you have to print "Case " also
Posted: Tue Oct 17, 2006 6:54 am
by Jan
Thanks. Got Accepted.
Posted: Wed Oct 18, 2006 5:24 pm
by Cho
Clarification: Can I simply assume that all the input points are distinct?
Posted: Wed Oct 18, 2006 7:44 pm
by sclo
There are no duplicate points or else my program will give RE for that.
Posted: Thu Oct 19, 2006 4:44 am
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?
1? or 2?
Posted: Thu Oct 19, 2006 4:49 am
by Jan
There are no duplicate points.