You are not logged in. Please login at www.codechef.com to post your questions!

×

URBANDEV - Editorial

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

Medium

PREREQUISITES:

sweep line, segment tree

PROBLEM:

Given N segments on Cartesian plane, each one is either vertical or horizontal, count the number of intersection points between any pair of the segments.

EXPLANATION:

General explanation

Let's imagine vertical line moving from very far left (say X=-inf) to very far right (say X=inf) -let's call this line as "sweeping line"-, at every moment this line is intersecting with some subset of horizontal segments so we can keep track with this subset as long as the sweeping line is moving, now whenever that line meets vertical segment, say it's endpoints are (X1,Y1) and (X2,Y2) such that X1=X2 and Y1 < Y2, then the answer to its query is the number of horizontal segments which are now intersecting with the sweeping line and their Y-coordinates is between Y1 and Y2.

so if we can find a way to quickly count number of horizontal segments in the subset which have Y-coordinates between any given range then we can answer the query of all vertical segments. however, we also need to support add/erasing segments from the subset.

note that we can do the same idea but with a horizontal sweeping line to answer the queries of horizontal segments.

representing the sweeping line and its movement technically

We want to find a way to store the subset of horizontal segments which are currently interesting with the sweeping line and support quickly adding new segment to this set and support removing existing segment from this set.

This can be done by consider the sweeping line as an array A of length 105 + 1 if there's currently segment intersecting with sweeping line at Y-coordinate equal to Y then we have A[Y] = 1 otherwise, we have A[Y] = 0, when we want to answer a query to vertical segment then we just need to find the sum of elements in this array inside a given range, so can use segment tree or Fenwick tree data structure.

to simulate the movement of the sweeping line we are only interested in some events that will occur during the movement of the sweeping line which are

  • The sweeping line meets with a vertical segment, because we need to answer its query

  • sweeping line intersect with new horizontal segment

  • sweeping line stop intersecting with a horizontal segment

so we create an array of events that will store all events of any of the above 3 types and sort them according the X-coordinates where it will happen, then we simply do the events in that order.

Corner Cases

  • The problem said "at least two other directions to continue their trip" so we should intersecting points that has extensions in 3 or 4 directions but not 2, that means an intersection point can be endpoint of at most of segment but not two, so for simplicity we can include the case that has 2 extensions then exclude them alone, so for now an intersecting can be an endpoint of 2 segments
  • when we sort the events in case two or more events have same X-coordinates then we put first events of adding new horizontal segments first, then the events of querying vertical segments and lastly the events of erasing horizontal segments, this is because an intersection point can be an endpoint of a segment.
  • also because an intersection point can be an endpoint of a segment, then the range sum query should be inclusive.

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 12 Nov '16, 10:41

kingofnumbers's gravatar image

6★kingofnumbers ♦
31614
accept rate: 0%

edited 17 Nov '16, 13:46


Setter's and tester's link are not working! Please fix it @admin

link

answered 16 Nov '16, 18:12

bansal1232's gravatar image

4★bansal1232
2.6k110
accept rate: 16%

Hi

Can someone explain the reason why my (brute force) code gives WA for subtask 1 (for subtask 2, it would definitely give TLE)? I checked all line segments pairwise and if they had any valid intersection, I incremented the total count and also the count for the respective line segments. Where is it going wrong?

Code link: solution

link

answered 16 Nov '16, 18:51

ksharma377's gravatar image

4★ksharma377
111
accept rate: 0%

Your solution fails for the test case:

2

1 2 3 2

2 1 2 2

The answer must be:

1

1 1

Your answer is:

0

0 0

The figure is in the form of the alphabet "T".

Happy coding ;)

(16 Nov '16, 23:09) aloochaat19985★

There's a typo, one of the two "sweeping line intersect with new horizontal segment" should be "sweeping line intersect with end of horizontal segment".

In short, given a vertical segment from (x,y1) to (x,y2) y2>y1, events to be determined are

  1. Horizontal segments (any) that lie between (y1+1,y2-1)
  2. Horizontal segments (don't begin or end at x) at y1 and y2.
link

answered 17 Nov '16, 11:03

noob333's gravatar image

5★noob333
10314
accept rate: 0%

Thanks, fixed!

(17 Nov '16, 13:46) kingofnumbers ♦6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,354
×1,812
×1,188
×150
×38
×17

question asked: 12 Nov '16, 10:41

question was seen: 2,724 times

last updated: 17 Nov '16, 13:46