描述
给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。
输入
第一行为正整数N，表示点的个数，接下来N行分别为这N个点所分割的各个圆弧长度
输出
所构成不重复矩形的个数
样例输入
8
1
2
2
3
1
1
3
3
1
2
2
3
1
1
3
3
样例输出
3
数据范围
N<= 20
方法分析与感悟
看到数据范围就松了一口气= =
我是这样想的，若有两条对角线（皆为这个圆的半径），那么这两条线所构成的就是矩形。
判断是否为对角线：两点构成的两弧长度相等则是
判断是否重复：在半个圆中，双重循环模拟两条对角线得到
我的程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | 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)
