shunfurh
编程介的小学生
2019-03-29 22:44

寻找两条最接近的路径的算法问题,采用C语言程序设计的办法如何解决的呢?

  • Golang
  • r语言
  • erlang

Problem Description
JFantasy has fallen in love with a beautiful girl (An ICPC volunteer?). Every afternoon, when the sun set, the girl comes out from her dorm, walks around the campus, and returns to her dorm. The girl’s walking path can be considered as a closed polyline. A closed polyline is a curve specified by a sequence of points (P1, P2, …, Pn) so that the curve consists of the line segments P1P2, P2P3, …, Pn-1Pn, PnP1. Note that two line segments may intersect, coincide or partially coincide with each other. The points P1, P2, …, Pn are also called vertices of the polyline. While the girl is walking along the path, JFantasy is standing at some point which is not lying on the path. During the girl’s walking, the spoony boy rotates himself such that he can always see the girl directly in front of him. The boy may sometimes rotate counter-clockwise, and sometimes rotate clockwise. If the boy stands at point P, let AP denote the total degrees the boy rotate counter-clockwise, and BP denote the total degrees the boy rotate clockwise. It is not difficult to see that AP – BP is a multiple of 360, because when the girl finishes walking, the boy faces in the same direction as when the girl starts walking. We define the rotation number of P to be (AP – BP) / 360.

LCQ is one of JFantasy’s G (G for good) friends. He has found JFantasy’s secret, and got an idea of making fun of him. He wants to put JFantasy at some point of which the rotation number is maximum given the walking path of the girl. To simplify the problem, we assume that the point where JFantasy can be put must be on a straight line. Formally, the problem can be stated as follows: Given the coordinates of (P1, P2, …, Pn), which specifies the girl’s walking path, you are asked to find the largest possible rotation number among all the points that are on the X axis, but not on the girl’s walking path.

Input
The input begins with a line containing an integer T (T<=100), which indicates the number of test cases. Each case begins with a line containing an integer N (2<=N<=1000), indicating the number of vertices of the girl’s walking path. The following N lines each contain two integers xi and yi (-1000<= xi, yi <=1000), indicating the coordinates of the ith vertex Pi.

Output
For each case, output the largest possible rotation number in a line.

Sample Input
3
2
1 2
2 1
6
1 -1
2 -1
2 1
3 1
3 0
1 0
5
1 1
-1 0
1 -1
0 1
0 -1

Sample Output
0
0
2

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

0条回答