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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

ICPC de Tryst

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures
• Algorithms > Graphs
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming
• Math > Combinatorics