描述
给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。
输入
第一行为正整数N，表示点的个数，接下来N行分别为这N个点所分割的各个圆弧长度
输出
所构成不重复矩形的个数
样例输入
8
1
2
2
3
1
1
3
3
1
2
2
3
1
1
3
3
样例输出
3
数据范围
N<= 20
方法分析与感悟
看到数据范围就松了一口气= =
我是这样想的，若有两条对角线（皆为这个圆的半径），那么这两条线所构成的就是矩形。
判断是否为对角线：两点构成的两弧长度相等则是
判断是否重复：在半个圆中，双重循环模拟两条对角线得到
我的程序
program fly;
var
a:array[1..100]of longint;
i,j,ilong,jlong,n,ans,c:longint;
function solve(x:integer):boolean;
var i,s:integer;
begin
s:=0;
repeat
s:=s+a[x];
inc(x);
if x>n then x:=x mod n;
if s>(c div 2) then exit(false);
until s=(c div 2);
exit(true);
end;
begin
// assign(input,'fly.in');
// assign(output,'fly.out');
// reset(input);
// rewrite(output);
readln(n);
for i:=1 to n do
begin
readln(a[i]);
c:=c+a[i];
end;
i:=0;
j:=0;
repeat
inc(I);
inc(ilong,a[i]);
j:=i+1;
jlong:=0;
inc(jlong,ilong+a[j]);
while (jlong<(c div 2)) do
begin
if (solve(i))and(solve(j)) then begin
inc(ans);
// writeln(i,' ',j);
end;
inc(j);
inc(jlong,a[j]);
end;
until ilong>=(c div 2);
writeln(ans);
// close(input);
// close(output);
end.
那10分没过、若有大神路过，请赐教！
评论 (0)
