#P18939. [Mladen Manev 2019 B3] drawing / 定长折线

[Mladen Manev 2019 B3] drawing / 定长折线

定长折线

给定平面上的两个点 P0=(x0,y0)P_0=(x_0,y_0)、Pn=(xn,yn)P_n=(x_n,y_n),以及 nn 个正整数 a1,…,ana_1,\ldots,a_n。

构造依次连接 P0,P1,…,PnP_0,P_1,\ldots,P_n 的折线,使第 ii 条线段的长度等于 aia_i。允许线段相交、顶点重合。若不存在这样的折线,报告无解。

输入格式

第一行四个整数 x0,y0,xn,ynx_0,y_0,x_n,y_n。第二行整数 nn。第三行 nn 个整数 aia_i。

输出格式

无解输出 NO。否则先输出 YES,再输出 n+1n+1 行,每行两个实数,表示 P0P_0 至 PnP_n 的坐标。

首尾点必须与输入一致;每条线段的长度与规定长度的绝对误差不超过 10−310^{-3}。

数据范围

2≤n≤10002\le n\le1000,1≤ai≤10001\le a_i\le1000,输入坐标的绝对值不超过 1000010000。

样例

0 0 6 0
2
5 5
YES
0 0
3 4
6 0

来源与数据说明

2019 年 Dr. Mladen Manev,B3,原题名 drawing。赛事资料,原文题面见附件 statement.pdf。

本题使用官方原始测试数据;评测接口按本站环境适配。总分为 100 分。