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

×

AMR14J - Editorial

PROBLEM LINK:

Practice
Contest

Editorialist: Lalit Kundu

DIFFICULTY:

MEDIUM

PRE-REQUISITES:

GEOMETRY, MATHS

PROBLEM:

N(<101) circle painted one after another. When two circles overlap, only the later painted one is fully visible, and the earlier painted one and its boundary are partly obscured by the later painted one. The organizers are interested in knowing the total length of the visible black boundary after all N circles have been painted.

EXPLANATION:

There can be two approaches to this:

APPROACH 1:

We find all the intersection points for each circle, that is, for each circle we find coordinates of all those points where any other circle intersects it. Each circle can have O(N) such points. Now, we sort such points in clockwise or counter-clockwise direction. And for each arc defined by two consecutive points in sorted array, we check if that arc can be counted in answer ie. if that arc lies below any other circle or not*. This checking can be done in O(N). So, overall complexity would be O(N3). * arc of circle i will lie below circle j(j>i), if that arc lies completely inside circle j.

APPROACH 2:

For i'th circle, for the j'th(0 ≤ j < i) circle, we find intersection points and with respect to a horizontal line, we define the polar angles.
So, we get all information like: i'th circle puts out from the answer the arc defined by angles theta1 to theta2 of circle j.(Note these angles are with respect to some horizontal or vertical line).
After this, we get for each circle all the invalid arcs. There could be atmost O(N) such arcs. Now, some of these might be overlapping, so we merge these interval arcs in O(N log N) using something similar to this.
After merging them into disjoint arc intervals, we find the length of covered boundary and add to answer the remaining length.
So, overall complexity would be O(N*N*log N).

We didn't go into minute implementation details because that you will get by simple googling. This implementation would be prone to bugs, so a lot of carefulness was required into implementing this.

SOLUTIONS:

Setter's solution

This question is marked "community wiki".

asked 14 Jan '15, 23:01

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%


The solution link is broken.

link

answered 29 Sep '18, 17:51

ankit_btech's gravatar image

4★ankit_btech
717
accept rate: 0%

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:

×15,852
×2,658
×647
×37
×1

question asked: 14 Jan '15, 23:01

question was seen: 3,324 times

last updated: 29 Sep '18, 17:51