程序设计比赛试题(13)

多边形

timelimit:1 seconds memlimit:32768 K Prev |Next

【问题描述】

在一个坐标平面上，给一个n个点的集合，能不能画出一个简单多边形（除相邻边外其他任意两条边没有公共点）。要求这个多边形的顶点集合就是给定的点集，而且多边形的边必须与x轴或y轴平行.更进一步,要求多边形相邻的边不平行,也就是说,多边形的边是一条横线段,接着一条竖线段,再接着一条横线段....

【要求】

【数据输入】输入包括多组数据.

输入数据的第一行包括一个整数t,表示有t组输入数据，t<10. 每组输入数据的第一行为一个整数n,(4 ≤ n ≤ 100000)

接下来的n行每行描述一个点的坐标,包括两个整数x y,( |x|,|y| ≤ 1000 )

【数据输出】

每个输入数据输出一行

如果可以画出要求的多边形,输出多边形的周长.如果存在多个这样的多边形，输出周长最小的。

如果不存在这样的多边形,输出-1

【样例输入】 1 8 1 2 1 0 2 1 2 2 3 2 3 1 4 0 4 2

【样例输出】 12

H数

timelimit:1 seconds memlimit:32768 K Prev |Next

【问题描述】

让我们来做做David Hilbert的一个练习题.

定义H数为4的正整数倍加1,比如: 1, 5, 9, 13, 17, 21, 25... 都是H数.可以证明两个H数相乘结果还是H数.类似于整数,我们也可以把H数分为1, H素数和H合数.一个H数为H素数,当且仅当,它除了1和自己之外,没有其他的H数整除它.除了1和H素数外,其他的H数都是H合数.比如9是H素数,因为除了1和9之外没有其他的H数整除9; 17和21也是H素数; 45是H合数，45=5×9，25也是H合数,因为 25=5×5.

你的任务是计算H半素数的个数. 一个H数是H半素数,当且仅当,它能分解成两个H素数的乘积.

这两个H素数可以是同一个数.比如25是H半素数,25=5×5。45也是H半素数, 45 = 5×9,而125不是H半