---{"category_name":"easy","problem_code":"GEO1","problem_name":"Geometry 1","problemComponents":{"constraints":"- $1 \\leq T \\leq 250$\n- $3 \\leq N \\leq 10^4$\n- $1 \\leq Q \\leq 10^4$\n- $0 \\leq x_i, y_i \\leq 2 \\cdot 10^6$\n- $1 \\leq v_i, t_i \\leq 10^5$\n- $1 \\leq v_i \\cdot t_i \\leq 10^5$\n- The sum $N$ over all testcases does not exceed $5 \\cdot 10^5$.\n- The sum $Q$ over all testcases does not exceed $5 \\cdot 10^5$.\n- The vertices of polygon are given in counter-clockwise order.\n- The internal angles of the given polygon are greater than $1^{\\circ}$. ","constraintsState":true,"subtasks":"**Subtask #1 (100 points):** original constraints","subtasksState":true,"inputFormat":"- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.\n- Each testcase contains $N + Q + 1$ lines of input.\n- The first line of each test case contains two space-separated integers $N, Q$.\n- $N$ lines follow. For each valid $i$, the $i^{th}$ of these lines contains two space-separated integers $x_i, y_i$, coordinates of the $i^{th}$ vertex of the polygon.\n- Next $Q$ lines follow. For each valid $i$, the $i^{th}$ of these lines contains two space-separated integers $v_i, t_i$, description of the $i^{th}$ query.\n","inputFormatState":true,"outputFormat":"For each query, output in a single line the final area covered by $N$ sides of the polygon. \n\nYour answer will be considered correct if its **relative** or **absolute** error does not exceed $10^{-2}$.\n","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"2\n4 1\n1 1\n2 1\n2 2\n1 2\n1 1\n3 2\n1 1\n2 1\n1 2\n1 1\n2 3","output":"9.0000000\n9.7426406\n230.8086578","explanation":"Below are the images for the respective test cases. Inner polygons are the ones at the start and the rays represent the distance traveled by the sides at the given speed in a given time. Outer polygons denote the final ones after the movements of the sides.\n\n**Test case $1$:**\n\n\u003Cimg src=\u0022https://s3.amazonaws.com/codechef_shared/download/Images/DAANISH/i2.png\u0022 width=\u0022450\u0022 height=\u0022378\u0022 /\u003E\n\n**Test case $2$**: $1^{st}$ query\n\n\u003Cimg src=\u0022https://s3.amazonaws.com/codechef_shared/download/Images/DAANISH/i1.png\u0022 width=\u0022450\u0022 height=\u0022378\u0022 /\u003E","isDeleted":false}}},"video_editorial_url":"https://youtu.be/pSKC74iZnrc","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1.5,"source_sizelimit":50000,"problem_author":"daanish_adm","problem_tester":"","date_added":"14-07-2021","tags":{"0":"aug21","1":"daanish_adm","2":"easy","3":"geometry"},"problem_difficulty_level":"Unavailable","best_tag":"","editorial_url":"https://discuss.codechef.com/problems/GEO1","time":{"view_start_date":1629117000,"submit_start_date":1629117000,"visible_start_date":1629117000,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=GEO1","is_proctored":false,"visitedContests":{},"layout":"problem"}---### Read problem statements in [Bengali](https://www.codechef.com/download/translated/AUG21/bengali/GEO1.pdf), [Mandarin Chinese](https://www.codechef.com/download/translated/AUG21/mandarin/GEO1.pdf), [Russian](https://www.codechef.com/download/translated/AUG21/russian/GEO1.pdf), and [Vietnamese](https://www.codechef.com/download/translated/AUG21/vietnamese/GEO1.pdf) as well.You are given a convex polygon with $N$ sides. You have to answer $Q$ queries. The $i^{th}$ query is described by two integers $v_i, t_i$. In this query, all sides of the polygon start moving parallel to their respective perpendicular vector away from the centroid with a constant velocity of $v_i \frac{units}{sec}$. Output the final area covered by $N$ sides of the polygon after time $t_i$ seconds.For each query, consider the initial coordinates of vertices of the given polygon.**Note:**- Since the input-output is large, prefer using fast input-output methods.- The problem requires high precision, so prefer using data types with a precision equivalent to long double in C++.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>