Posted: Mon Oct 02, 2006 7:02 pm
thanks I will try it myself at least for few hours...
before further assistance..
before further assistance..
I got AC thiniking on your input set
Page 2 of 3
Posted: Mon Oct 02, 2006 9:36 pm
thanks little joey !
I got AC thiniking on your input set
I got AC thiniking on your input set
Posted: Mon Oct 02, 2006 10:30 pm
how can I chek that is the polygon simple or not?
I think if I want check for it , my program will get TLE
I think if I want check for it , my program will get TLE
Posted: Tue Oct 03, 2006 2:40 am
@little joey...
ok gave up...
what additonal step r u talking about....
ok gave up...
what additonal step r u talking about....
Posted: Wed Oct 04, 2006 3:15 pm
Good question. The test data for this problem is too weak.rammestain wrote:how can I chek that is the polygon simple or not?
I think if I want check for it , my program will get TLE
Posted: Wed Oct 04, 2006 4:00 pm
u mean simulating the process of choosing point would suceed ....
but i don't wanna do that....
@little joey
what additonal step is required...
but i don't wanna do that....
@little joey
what additonal step is required...
Posted: Wed Oct 04, 2006 4:04 pm
Label all possible points (there are only 4 million of them) with theirvinay wrote:u mean simulating the process of choosing point would suceed ....
but i don't wanna do that....
@little joey
what additonal step is required...
minimum distance from mall A. From these chose the closest one
that is a point on mall B. You can do this in o(4 million) operations.
Posted: Wed Oct 04, 2006 4:44 pm
I'm sorry, but my algorithm is incorrect (although I get Accepted), for the reason rammestain mentioned. For the inputvinay wrote:@little joey
what additonal step is required...
Code: Select all
1
6
0 0
1 0
0 1
2 1
1 2
2 2
Posted: Wed Oct 04, 2006 4:50 pm
Yes the test data is too simple. So one possible "fix" is to reword the question ... but it isn't that easy: you have to replace non-intersecting by something like "distinct vertices and any pair of edges share at most one point"little joey wrote:I'm sorry, but my algorithm is incorrect (although I get Accepted), for the reason rammestain mentioned. For the inputvinay wrote:@little joey
what additonal step is required...it gives 8, but the resulting polygon is not simple. So either the testdata is too simple, or it is not correct. I'm afraid I can't help you until I've corrected my own program...Code: Select all
1 6 0 0 1 0 0 1 2 1 1 2 2 2
If you insist on implementing the problem as specified, you have to worry about segment intersection. There are algorithms for this but sub-quadratic is complicated.
Posted: Wed Oct 04, 2006 9:25 pm
one easy way to check if resulting polygon is 'simple' is to start from any point and move along lines , flagging points as you go, untill you hit already flagged point.
then you just check if in that process you flaged all points.
of course, it rely on being able to see which points are connected, but that is usually what your first part of solution does when you try to create polygon ;p
anyway, this approach is fast enough - even if you use PASCAL as I did
then you just check if in that process you flaged all points.
of course, it rely on being able to see which points are connected, but that is usually what your first part of solution does when you try to create polygon ;p
anyway, this approach is fast enough - even if you use PASCAL as I did
Posted: Wed Oct 04, 2006 9:28 pm
Your approach fails to check for self-intersection.lost wrote:one easy way to check if resulting polygon is 'simple' is to start from any point and move along lines , flagging points as you go, untill you hit already flagged point.
then you just check if in that process you flaged all points.
of course, it rely on being able to see which points are connected, but that is usually what your first part of solution does when you try to create polygon ;p
anyway, this approach is fast enough - even if you use PASCAL as I did
Posted: Wed Oct 04, 2006 9:46 pm
i think that first part of my solution, one that generate polygon, can not generate self-intersecting one
but i will have to check that ;p
but i will have to check that ;p
Posted: Wed Oct 04, 2006 10:02 pm
ah, i just found that my approach for generating polygon CAN generate self-intersecting polygons, as gvcormac suggested ;p
one simple test case would be:
1
6
0 0
0 1
1 0
1 2
2 1
2 2
anyway, it turned out that i had only slightly to modify my algorithm in order to detect if there is some line crossing during polygon creation. It even run at about same speed as previous one (was x53, now its x55)
one simple test case would be:
1
6
0 0
0 1
1 0
1 2
2 1
2 2
anyway, it turned out that i had only slightly to modify my algorithm in order to detect if there is some line crossing during polygon creation. It even run at about same speed as previous one (was x53, now its x55)
Posted: Wed Oct 04, 2006 10:05 pm
Again, the test data is too weak. A quadratic time solution to line crossing should not be fast enough.lost wrote:ah, i just found that my approach for generating polygon CAN generate self-intersecting polygons, as gvcormac suggested ;p
one simple test case would be:
1
6
0 0
0 1
1 0
1 2
2 1
2 2
anyway, it turned out that i had only slightly to modify my algorithm in order to detect if there is some line crossing during polygon creation. It even run at about same speed as previous one (was x53, now its x55)
Posted: Wed Oct 04, 2006 10:20 pm
well, i'm not using quadratic time solution to detect line crossing. solution that i used is fast enough, but it rely on same assumption that rest of my solution rely on.
as long as that assumption is correct, my intersection detection will work fast.
if that assumption is invalidated by changing test data, then not only my intersection will not work, but rest of my solution as well
and since that assumption is not something that i would normally assume for test data (in fact, my first solution did not assume it, and it had TE), i would have to agree with you that test data is weak ;p
as long as that assumption is correct, my intersection detection will work fast.
if that assumption is invalidated by changing test data, then not only my intersection will not work, but rest of my solution as well
and since that assumption is not something that i would normally assume for test data (in fact, my first solution did not assume it, and it had TE), i would have to agree with you that test data is weak ;p