Special points of a polygon

0

0 votes
Mathematics, Basic Geometry, Projection, Math, Projections
Problem

A farm is a convex polygon that contains n points on a Cartesian plane. You want to hit a fence at a special point to break it. The special point is on the boundary of fence whose distance from you is minimum.

You are required to determine the special point.

Input format

  • First line: n and point P(x,y) (3n105)(109Px,Py109) denoting the number of points in the Convex polygon and your position respectively
  • Each of the next n lines: Two space-separated integers x and y (109x,y109) denoting points on the fence.
    Note: They are guaranteed to be in the clockwise or counter-clockwise direction.

Output format

Print two values x y denoting the x and y coordinates of the point that lies on the boundary and is nearest to you.

If there are multiple correct answers, then you can print any of them. Your answer can be considered correct if the distance of the special point from your position differs from the optimal distance by an absolute error of 109.

Sample Input
3 2 2
1 1
100 100
1 100
Sample Output
2.000000000000 2.000000000000
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The point (2,2) lies on the edge joining (1,1) and (100,100). Thus it's the nearest point.

Contributers:
Editor Image

?