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

×

AVNRLIN - Editorial

1
1

PROBLEM LINK:

Practice
Contest

Author: Amit Kumar Pandey
Editorialist: Arkapravo Ghosh

DIFFICULTY:

EASY

PREREQUISITES:

Math

PROBLEM:

A point (x, y) and n+1 lines each of which describes a line is given. The n+1 lines describe a sequence of lines starting from the starting point with n turns. It is required to find out if the initial and the final points are same.

EXPLANATION:

We are given the starting point of the polygon.
We are also given the sequence of n+1 lines starting from the starting point(x, y). We just need to check if the starting and the ending points are same.
The starting point is given. We just need to find the intersection of the first and the last given lines and that gives our ending point, where Flash stops. So, we just need to consider the first line, i.e. a1, b1, c1 and the last line a(n+1), b(n+1), c(n+1), i.e. the last line. We can now find the intersection of these two lines and check if is equal to the given starting point.
Now, given two lines a1x + b1x + c1 and a2x + b2y + c2, we can find the intersection of the lines by the formula:-
x' = (b1c2 - b2c1)/(a1b2 - a2b1)
y' = (c1a2 - a1c2)/(a1b2 - a2b1)
Now, we just need to check if x = x' and y = y', i.e. the initial point is same as the final point.
We also need to take care of the case where n=1, since no polygon can be formed with 1 turn(i.e. two sides), we need atleast two turns(i.e. atleast three sides). You can find the author's and my solution below. Hope this helps.:)

AUTHOR'S AND EDITORIALIST'S SOLUTIONS:

Author's solution can be found here.
Editorialist's solution can be found here.

RELATED PROBLEMS:

*AVHNLIN

This question is marked "community wiki".

asked 09 Jun '18, 20:17

horsbug98's gravatar image

4★horsbug98
3436
accept rate: 21%

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:

×877
×81
×81
×23
×1
×1

question asked: 09 Jun '18, 20:17

question was seen: 107 times

last updated: 09 Jun '18, 20:17