找合法三角形

题目传送门

大致思路

将数组升序排序,对每一个长度分别计算能构成的不同三角形:
等腰,等边另外算
三边都不相同的三角形:利用"三指针",说是三指针,其实感觉是双指针,两个指针在当前长度之前滑动,当前指针在计算时是不动的

Code

void solve(){
    int n;
    cin>>n;
    vector<pair<int,int>> a(n);
    for(int i=0;i<n;i++) cin>>a[i].first>>a[i].second;
    sort(all(a));
    int ans=0;
    for (int k=0; k<n; k++) {
        if (a[k].second>=3) ans++;//等边三角形
        if (a[k].second>=2) ans+=k;//自己出两条边的等腰
        for (int i=0; i<k; i++) if (a[i].first*2>a[k].first && a[i].second>=2) ans++; //自己出一条边的等腰
        //三条边都不一样
        int left=0, right=k-1;
        while (left<right) {
            if (a[left].first+a[right].first>a[k].first) {
                ans+=(right-left);
                right--;
            }
            else left++;
        }
    }
    cout<<ans<<el;
}