查看题目 Show Problem
题目:矩形计数
问题编号:698
题目描述
给出圆周上的N个点，请你计算出以这些点中的任意四个为四个角，能构成多少个矩形。
点的坐标是这样描述的，给定一个数组v[1..N]，假设圆心为(0，0)，圆的周长C=∑v[1..N] ，第一个点坐标为(0，C/(2π))。从第一个点开始，顺时针沿圆周走v1个单位长度，此时坐标为第二个点的坐标，再走v2个单位长度，此时为第三个点的坐标，当走完v1，v2..vi个距离后，为第i+1个点的坐标（全过程都是沿圆周顺时针）。特别的，走完v1，v2..vn个距离后，就会回到第一个点。
对于100%的数据，有N<=20，V数组中的所有元素的值<=100。
输入格式
输入共N+1行。
第一行为正整数N。
接下来N行每行一个正整数。其中第i+1行表示的是v[i]。
输出格式
输出共1行，一个整数，表示能构成的矩形的个数。
样例输入
8
1
2
2
3
1
1
3
3
样例输出
3
//样例解释[img]http://www.rqnoj.cn/ProblemPic/P698-101656.png[/img]
观察图片，易发现圆内的内接矩形对角线交点必过圆心（初中证明……）
所以只要找到所有对角线就行了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cstdlib>
using namespace std;
#define MAXN (100+10)
int n,c=0,m=0,a[MAXN];
int main()
{
scanf("%d",&n);
a[1]=0;
for (int i=2;i<=n;i++)
{
scanf("%d",&a[i]),c+=a[i];
if (!a[i]) i--,n--;
else a[i]=c;
}
int p;
scanf("%d",&p);c+=p;
int l=1,r=1;
while (r<=n&&l<=n)
{
if (a[r]-a[l]==c/2) {/*cout<<l<<' '<<r<<endl;*/m++;l++;}
else if (a[r]-a[l]<c/2) r++;
else l++;
}
cout<<m*(m-1)/2<<endl;
return 0;
}