All Tracks Math Problem

Expected distance of point from polygon
Tag(s):

Medium

Problem
Editorial
Analytics

You are given a Simple Polygon $$P$$ in $$XY$$ plane with $$n$$ vertices, given in clockwise OR anticlockwise order, and a point $$p$$ in the same plane.
All the vertices of $$P$$ and point $$p$$ have integer coordinates.

A point $$q$$ is chosen uniformly randomly inside the polygon. Find the expected euclidean distance of $$q$$ from $$p$$

Input

  • The first line contains $$n$$, the number of vertices of polygon $$P$$.

  • The next line contains two integers $$(x_0,y_0)$$, the coordinates of point $$p$$

  • $$i^{\text{th}}$$ of the next $$n$$ lines contains two integers $$(x_i,y_i)$$, the coordinates of $$i^{\text{th}}$$ vertex of polygon.

Output
Print only one line containing the expected distance of a point randomly chosen inside $$P$$ from $$p$$, rounded to the nearest integer.

Constraints

  • $$ n \le 10^5 $$

  • $$ 0 \le x_i,y_i \le 10^6$$, for all $$0 \le i \le n$$

  • All points in the input are distinct.

SAMPLE INPUT
4
3 3
1 1
1 5
5 5
5 1
SAMPLE OUTPUT
2
Explanation

The expected distance of center of a square of length $$4$$ from a point chosen randomly inside it is $$ \approx 1.5304 $$

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

IIT Delhi

Challenge Name

ICPC de Tryst

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications