1307

1307 - Counting Triangles

Time Limit: 2 second(s)

Memory Limit: 32 MB

You are given N sticks having distinct lengths; you have to form some triangles using the sticks. A triangle is valid if its area is positive. Your task is to find the number of ways you can form a valid triangle using the sticks.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer N (3 ≤ N ≤ 2000). The next line contains N integers denoting the lengths of the sticks. You can assume that the lengths are distinct and each length lies in the range [1, 10⁹].

Output

For each case, print the case number and the total number of ways a valid triangle can be formed.

Sample Input

Output for Sample Input

3 12 5 4 9

1 2 3 4 5 6

100 211 212 121

Case 1: 3

Case 2: 7

Case 3: 4

PROBLEM SETTER: JANE ALAM JAN

题意：给你的边能构成多少个三角形。

思路：先暴力组合两条边，然后二分查询第三条边即可。

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<string.h>
 5 #include<queue>
 6 #include<stdlib.h>
 7 #include<math.h>
 8 #include<stack>
 9 #include<vector>
10 #include<map>
11 using namespace std;
12 typedef long long LL;
13 int ans[2005];
14 typedef struct pp
15 {
16     short int x;
17     short int y;
18 } ss;
19 ss ak[4000005];
20 int main(void)
21 {
22     int i,j,k;
23     scanf("%d",&k);
24     int s;
25     for(s=1; s<=k; s++)
26     {
27         int n,m;
28         scanf("%d",&n);
29         for(i=0; i<n; i++)
30         {
31             scanf("%d",&ans[i]);
32         }
33         sort(ans,ans+n);
34         int cnt=0;
35         for(i=0; i<n; i++)
36         {
37             for(j=i+1; j<n; j++)
38             {
39                 ak[cnt].x=i;
40                 ak[cnt].y=j;
41                 cnt++;
42             }
43         }
44         LL sum=0;
45         for(i=0; i<cnt; i++)
46         {
47             int l=0;
48             int r=n-1;
49             int maxx=max(ans[ak[i].x],ans[ak[i].y]);
50             int minn=min(ans[ak[i].x],ans[ak[i].y]);
51             int id=0;
52             l=0;
53             r=n-1;int id1=-1;
54             while(l<=r)
55             {
56                 int mid=(l+r)/2;
57                 if(ans[mid]+minn>maxx)
58                 {
59                     id1=mid;
60                     r=mid-1;
61                 }
62                 else l=mid+1;
63             }
64             l=0;
65             r=n-1;int id2=-1;
66             while(l<=r)
67             {
68                 int mid=(l+r)/2;
69                 if(ans[mid]<maxx+minn)
70                 {
71                     id2=mid;
72                     l=mid+1;
73                 }
74                 else r=mid-1;
75             }
76             if(id1!=id2)
77             {
78                 sum+=id2-id1+1;
79                 if(ak[i].x>=id1&&ak[i].x<=id2)
80                     sum--;
81                 if(ak[i].y<=id2&&ak[i].y>=id1)
82                     sum--;
83             }
84         }
85         printf("Case %d: ",s);
86         printf("%lld
",sum/3);
87     }
88     return 0;
89 }

油！油！you@