#P6027. 轴对称

    ID: 4888 Type: RemoteJudge 1000ms 125MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>计算几何2020Special Judge

轴对称

题目背景

小 W 学习了轴对称变换。

题目描述

小 W 觉得轴对称变换实在太好玩了,于是在平面上随机点了 nn 个点 A1,A2,,AnA_1,A_2,\cdots,A_n,然后进行了一系列轴对称变换,得到了 B1,B2,,BnB_1,B_2,\cdots,B_nnn 个点,其中 A1A_1 得到 B1B_1,以此类推。

可是他突然忘记自己是怎么变换到的了,所以他请你帮他找到一组步数尽量少的合法的变换。

输入格式

第一行一个整数 nn,表示点的个数。

接下来 nn 行,第 i+1i+1 行两个实数 x,yx,y,表示 AiA_i 的横、纵坐标。

接下来 nn 行,第 i+n+1i+n+1 行两个实数 x,yx,y,表示 BiB_i 的横、纵坐标。

输出格式

第一行一个整数 kk ,表示最少的步数。

接下来 kk 行,第 i+1i+1 行三个实数 A,B,CA,B,C,表示第 ii 次轴对称变换的轴为直线 Ax+By+C=0Ax+By+C=0

2
1.000000 1.000000
2.000000 2.000000
4.000000 4.000000
3.000000 3.000000

1
1.000000 1.000000 -5.000000

提示

样例解释

提示

对于直线 Ax+By+C=0Ax+By+C=0,如果 BB 非零,那么它就是一次函数 y=ABxCBy=-\dfrac ABx-\dfrac CB 的图像;否则,它表示一条垂直于 xx 轴的直线 x=CAx=-\dfrac CA

本题带有 SPJ\text{SPJ}因为某种原因,本题不提供 SPJ\text{SPJ} 给选手。

对于每个测试点,如果你的 kk 正确,则获得 30%30\% 的分数;

接下来,我们将对 A1,A2,,AnA_1,A_2,\cdots,A_n 分别进行你给的 kk 次轴对称变换,记 AiA_i 得到的点为 CiC_i。如果对于所有的 iiBiB_iCiC_ix,yx,y 坐标之差的绝对值都不超过 10210^{-2},则你获得 100%100\% 的分数。

如果你只想输出 kk,也请在后面随意输出一些值,防止 UKE\text{UKE}

数据范围

测试点编号 n=n= 构造数据时翻折的次数
1,2 11 1\le1
3,4 22 10\le10
5,6 55 103\le10^3
7,8,9,10 1010 105\le10^5

对于所有数据,1n101\le n\le10x,y105|x|,|y|\le 10^5

所有数据点已经经过 SPJ\text{SPJ} 验证无误。

请保证你的输出中的所有 A,B,CA,B,C 满足 A,B,C105|A|,|B|,|C|\le 10^5