【lightoj1307】Counting Triangles-蒲公英云

【lightoj1307】Counting Triangles

J - J 圆周率用acos(-1.0) 使用longlong

Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu

Submit Status Practice LightOJ 1307 uDebug

Description

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, 109].

Output

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

Sample Input

3 12 5 4 9

1 2 3 4 5 6

100 211 212 121

Sample Output

Case 1: 3

Case 2: 7

Case 3: 4

比赛时没TLE豁然开朗，原来用二分可以轻松解决超时问题，看来二分更多的时候是用来优化程序的，我喜欢这种题。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int a[2005];
bool judge(int mid,int i,int j) {
    if(a[i]+a[j]>a[mid]&&a[mid]-a[i]<a[j]) {
        return true;
    }
    return false;
}
int main() {
    int T,p=0;
    scanf("%d",&T);
    while(T--) {
        int n;
        scanf("%d",&n);
        for(int i=0; i<n; i++) {
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        int ans=0;
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                int cnt=0;
                int l=j+1,r=n-1;
                while(l<=r) {
                    int mid=l+r>>1;
                    if(judge(mid,i,j)) {
                        cnt=mid;
                        l=mid+1;
                    } else {
                        r=mid-1;
                    }
                }
                if(cnt)
                    ans=ans+cnt-j;
            }
        }
        printf("Case %d: %d\n",++p,ans);
    }
    return 0;
}