天津市组队赛99tianjin.doc

NOI'99 天津队选拔赛试题 1999.3

说明:(1) 考试时间为3.5小时.
(2) 采用黑箱测试办法,一般不查看选手的程序.对每个测试数据,运行时间一般不得超过15秒 (486机型环境).
(3) 不能在程序中直接写结果.

一．(求素数) (20分)
从键盘上输入一个正整数t(t≤14),在屏幕上输出满足条件10t<N<10t+1的最小素数与最大素数.
(说明:在PASCAL系统下,使用COMP型数据或DOUBLE型数据,可分别得到19位和15位以上的准确数字数.其运算基本上与实型(REAL)一致.使用该类型数据时须加编译要求{$N+}.当然,使用其它类型数据也可以实现本题要求.)

二. (同心方阵) (30分)
一个N阶纵横图是指一个N×N的数字方阵,它满足:
(1) 该方阵由数字1,2,...,N×N组成,每个数字恰好只使用一次.
(2) 每行,每列及每条对角线上的N的数字之和相同.
一个N阶亚纵横图是指一个N×N的数字方阵,它满足:
(1) 该方阵由N×N个连续的自然数组成,每个数字恰好只使用一次.
(2) 每行,每列及每条对角线上的N的数字之和相同.
对于奇数N, N阶同心方阵是指:
(1) 它是一个N阶纵横图.
(2) 从方阵中心(第(N+1)/2行,第(N+1)/2列)向外扩展,可依次得到3阶,5阶,...,N-2阶亚纵横图.
编程要求: 从键盘上输入一个奇数N(11≥N≥5),利用文本文件先输出N,再按方阵的形式输出一个N阶同心方阵,同一行各数字用空格隔开. 或者在屏幕上显示无解的信息.

三.(分割多边形) (50分)
预备知识:平面上的点可用坐标(X,Y)表示,X,Y为绝对值不超过10000的整数.平面上的直线L可用A*X+B*Y+C=0表示,其中A,B,C为常数.点(X1,Y1)在直线L上的充分必要条件是 A*X1+B*Y1+C=0.两个点(X1,Y1),(X2,Y2)在直线L的同侧的充分必要条件是 (A*X1+B*Y1+C)与(A*X2+B*X2+C)同号.由三个点(X1,Y1),(X2,Y2),(X3,Y3)构成的三角形的面积等于 0.5*│(X2-X1)*(Y3-Y1)-(Y2-Y1)*(X3-X1)│,这里│a│表示数a 的绝对值.一个多边形为凸多边形的充分必要条件是:对任意给定的一条边,其余各顶点都在该边所在的直线的同侧.
输入:由文本文件DATA_99.3按下述格式输入一个N边形的已知数据:
第1行:整数N (200≥N≥4,N为多边形的边数)
第 2--N+1 行: 每行两个整数,中间用空格隔开 (第i行为N边形第i-1个顶点坐标按逆时针方向排列,顶点号(1--N)不得改动).
编程要求:
(1)(20分) 判断所给的多边形是否为凸多变形.在屏幕上显示有关信息.
(2)(30分) 对于凸多边形,则应求出一条对角线,它将凸多边形分割成两部分,这两部分的面积之差为最小.最后在屏幕上输出:① 该对角线对应的两顶点的编号及坐标.② 两部分的面积及面积之差.