背景

送分的题目总是要有的。

描述

给出两个多边形,请判断它们之中哪个更接近圆形。

每个人对“接近圆形”的定义或许会不同,所以可以参考下面的样例来确定判断标准。数据保证,如果将所表示的图形画出来,能让人立刻直观地判断出“谁更圆”。

输入格式

输入文件第一行为一个整数T,表明一共有T组数据。

每组数据的第一行为两个整数n_1和n_2,表示两个多边形的边数。

第二行为n_1对实数,每对实数(x,y)表示了第一个多边形的每个顶点。

第三行为n_2对实数,每对实数(x,y)表示了第二个多边形的每个顶点。

顶点按照顺序给出,并且保证多边形不自交。

输出格式

输出T行,每行一个整数。输出1代表第一个多边形更圆,而2代表第二个多边形更圆。请不要输出空格等其他字符。

样例输入

3
3 4
1732 -1000 0 2000 -1732 -1000
1000 1000 1000 -1000 -1000 -1000 -1000 1000
4 4
1000 0 0 100 -1000 0 0 -100
1000 0 0 200 -1000 0 0 -200
6 6
1000 1000 0 500 -1000 1000 -1000 -1000 0 -500 1000 -1000
1000 1000 0 1500 -1000 1000 -1000 -1000 0 -1500 1000 -1000

样例输出

2
2
2

数据范围与约定

  • 第1个测试点满足:所有的多边形都可以近似看做正多边形。
  • 第2个测试点满足:每一组的两个多边形边数相同,且其中一个可以近似看做正多边形。
  • 第3个和第4个输入文件满足:每组数据当中,要么两个多边形都是正多边形,要么两个多边形边数相同且其中一个是正多边形。
  • 第5个和第6个输入文件满足:n_1=n_2=3。
  • 第7个和第8个输入文件满足:n_1,n_2≤1000。
  • 第9个和第10个输入文件没有特殊的特征。
  • 所有的输入满足:T=10,3≤n_1,n_2≤30,000,|x|,|y|≤10,000,且如果将所表示的图形画出来,能让人立刻直观地判断出“谁更圆”。

样例解释

第一组数据大体上为一个正三角形和一个正方形,显然正方形更接近圆。

第二组数据为两个菱形,显然后者更接近圆。

第三组数据为两个六边形,显然后者更接近圆。

评分标准

对于所有数据,除样例外,T=10。

由于对于“接近圆形”的定义或许会不同,只要你的输出有90%以上是正确的,即输出的前10行有至少9行是正确的,就得该测试点的满分。

来源

原创