thanks I will try it myself at least for few hours...
before further assistance..
11106 - Rectilinear Polygon
Moderator: Board moderators
-
rammestain
- New poster
- Posts: 18
- Joined: Fri Apr 21, 2006 11:34 am
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.
-
little joey
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 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
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.
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
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
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)
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)
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