luogu#P8309. 〈 TREEのOI 2022 Spring 〉Dimension-2 Square

〈 TREEのOI 2022 Spring 〉Dimension-2 Square

题目背景

本题可能轻微卡精度,建议改用 long double\tt long\ double

正月十五夜空中。

一行人望着一棵树,一棵飘在天上的树,期待着它变成一个环。

这棵树有 44 个节点。

“它变成环了!”有人大喊。
我顿时向天上望去……

多么标准的正方形啊!无论哪个天文学家过来测量,它的角都是标准的 9090^{\circ},它的边都是完美的 1:1:1:11:1:1:1……

只见那棵树,不,那标致而又完美的环,缓缓飞过,恰巧嵌在了那轮明月中心……

题目描述

给定平面直角坐标系上 44 个点的坐标。

你需要使用 %法 魔法,做一个正方形,使得这 44 个点分别在正方形每条边的直线上。

输入格式

本题采用多组数据评测。

第一行,输入一个数 TT,表示数据组数。

对于每组数据,共 44 行,每行两个整数 xi,yix_i,y_i,表示点的坐标。

输出格式

对于每组数据,输出共 44 行,每行两个实数,表示正方形上的四个点的坐标。你需要保证给出的第 ii 个点位于正方形的第 ii 个和第 i mod 4+1i\ \text{mod}\ 4+1 个顶点形成的边上,且给出的第 ii 个点和第 i mod 4+1i\ \text{mod}\ 4+1 个点所在的边为邻边。

1
235 423
544 345
563 645
453 435
380.43769007 531.90429895
395.56394564 543.23089701
406.89054360 528.10464158
391.76428803 516.77804352

提示

本题采用 SPJ\tt SPJ

如答案不唯一,输出一种即可。
四边长度的之差 102\le 10^{-2} 且相邻两边夹角在 π2±102\frac{\pi}{2}\pm10^{-2} 内且设给定的点为 (p,q)(p,q),则存在一点 (p,q+k) (k1)(p,q+k)\ (|k|\leq1) 在对应边所在直线上即可 AC\tt \green {AC}

对于 30%30\% 的数据,T=1,xi,yi103T=1,|x_i|,|y_i|\le10^3

对于 70%70\% 的数据,1T5×104,xi,yi1061\leq T\leq 5\times 10^4,|x_i|,|y_i|\le10^6

对于 100%100\% 的数据,1T5×105,xi,yi1091\leq T\leq 5\times 10^5,|x_i|,|y_i|\le10^9

数据保证任意两点连成的 66 直线两两之间互不垂直,且没有平行于轴的直线,任意三点不共线。保证不存在一组解的边与轴平行。保证有解。

为了数据的精确性,您输出时至少需要保留 88 位小数。