HBC224027回文,Manacher,字符串ProblemD:LastWill题解 (davidisafarmerandhasalargefarm)

一个忧伤的美男子 算法基础篇 35 0
不断提升技能,才能在职场中立于不败之地!全网最全C++题库,助您成为编程领域的佼佼者。
David is a farmer and has a large farm. The shape of the farm is a square. A square is a quadrilateral that has four equal sides and four equal angles. The length of any side of David’s farm is on

David is a farmer and has a large farm. The shape of the farm is a square. A square is a quadrilateral that has four equal sides and four equal angles. The length of any side of David’s farm is one kilo meter, so the area of his farm is slightly greater than the total area of 140 standard football fields. David is old and very ill. He feels that his days are numbered. Worrying that his spouse Dora and their three children, Alice, Bob, and Cliff, will have a dispute over the ownership of the farm after he passes away, he plans to divide the farm into four parts, and then to allocate each part to one of his family members. He decides to write his last will as follows. 1.Assume that the shape of the farm is a square ABCD where A = (0, 0), B = (1, 0),C = (1, 1), D = (0, 1). 2.Let E = (0.5, 0), F = (1, 0.5), G = (0.5, 1), H = (0, 0.5) be the midpoints of ABˉbar{AB}ABˉ, BCˉbar{BC}BCˉ,CDˉbar{CD}CDˉ, DAˉbar{DA}DAˉ, respectively. 3.Let area(P RQS) to denote the area of the quadrilateral P QRS. 4.Please find a point X strictly inside the square ABCD such that      area(AEXH) : area(BF XE) : area(CGXF) = p : q : r  Note that X cannot be on the boundary of the square ABCD. 5.Allocate the land in AEXH, BFXE, CGXF, DHXG to Alice, Bob, Cliff and Dora, respectively. David is still adjusting the numbers. p, q, r, and his lawyer, Reed, has to read David’s last will carefully. Reed finds that it is impossible to find such point X if David gives an improper set of the numbers such as p = 1, q = 2, r = 1. However, there are proper sets of the numbers p, q, r that allow us to find the point X satisfying David’s last will. For instance, let p : q : r = 2 : 3 : 2, the following figure shows a possible position of X.          Figure 2: area(AEXH) : area(BFXE) : area(CGXF) = 2 : 3 : 2 Please write a program to help Reed to determine whether it is possible to find a point X satisfying David’s last will for a given set of numbers p, q, r. If possible, please output one possible position of X to Reed.

HBC224027回文,Manacher,字符串ProblemD:LastWill题解
(davidisafarmerandhasalargefarm)-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
成为编程大师,不再是梦想!全网最全C++题库,助您开启编程新篇章。

标签: HBC224027回文 Manacher 字符串ProblemD:LastWill题解