StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
20628315
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2013-12-17T07:27:05.300
FavoriteCount
0
LastActivityDate
2013-12-17T08:50:00.353
LastEditDate
2017-05-23T10:25:28.003
LastEditorUserId
-1
OwnerUserId
1896870
ParentId
20626700
PostTypeId
2
Score
1
ViewCount
0
LastEditorDisplayName
text
Body
I don't have enough reputation to leave a comment directly, so I'll be detailed and leave an answer here. Your algorithm does pair wise computation with a nested loop and has O(n2) temporal complexity, that's why your algorithm is slow for large inputs (large here doesn't mean the coordinate values, but the number of light houses). First let's see what we could do to optimize, with a sample input: 3 1 1 (Pa) 2 2 (Pb) 3 3 (Pc) With your algorithm, the execution logic would be: <ol> <li>count=0</li> <li>Pa and Pb is a pair? True, count++</li> <li>Pa and Pc is a pair? True, count++</li> <li>Pb and Pc is a pair? True, count++</li> <li>output count</li> </ol> There are actually redundant computations which could be eliminated: Determine whether a newly added light house could be illuminated by existing light houses. Note that Pa's NE region actually contains Pb's NE region, so if a new light house falls into Pb's NE region, that implicitly means it's illuminated by Pa, as well as Pb. So if we have Pa and Pb in the sea and add Pc, we actually don't need to compute twice with Pa and Pb separately. Say if we have the following record which records the the illumination intersection areas of light houses: a. count=0; R={} b. add Pa, R={[(-∞,-∞),(1,1)]->[Pa],[(1,1),(∞,∞)]->[Pa]} ([(-∞,-∞),(1,1)] and [(1,1),(∞,∞)] define two rectangular areas with their diagonal points) c. add Pb, Pb is in [(1,1),(∞,∞)] (that means [Pa] can illuminate Pb), find all light houses in [Pa] that could be illuminated by Pb, that's Pa, count+=1, R={[(-∞,-∞),(1,1)]->[Pa,Pb],[(-∞,1),(1,2)]->[Pb],[(1,-∞),(2,1)]->[Pb],[(1,1),(2,2)]->[Pa,Pb],[(1,2),(2,∞)]->[Pb],[(2,1),(∞,2)]->[Pb],[(2,2),(∞,∞)]->[Pa,Pb]} d. add Pc, Pc is in [(2,2),(∞,∞)], find all light houses in [Pa,Pb] that could be illuminated by [Pa,Pb], that's Pa,Pb, count+=2, update R (will be too long so I'll just omit it here) <img src="https://i.stack.imgur.com/g3bLt.png" alt="enter image description here"> One data structure you may want to represent R is a segment tree<a href="https://i.stack.imgur.com/g3bLt.png" rel="nofollow noreferrer">1</a>. The segment tree applicable here would be two-dimensional. I suggest you have a look at existing post like <a href="https://stackoverflow.com/questions/17225753/how-to-code-2d-segment-tree">How to code 2D segment tree?</a> and try to implement your own. <a href="https://i.stack.imgur.com/g3bLt.png" rel="nofollow noreferrer">1</a> <a href="http://en.wikipedia.org/wiki/Segment_tree" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Segment_tree</a>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POImprove efficiency "lighthouse"
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USCommunity
UserOwnerUserId
1. USMengdong Yang
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.