Editorial for HSG THPT Thanh Hóa 2020 - Tam giác

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Gọi ~x,y,z~ lần lượt là độ dài của ba cạnh tam giác. Không mất tính tổng quát, ta giả sử ~x \le y \le z~.

Ta có các tính chất:

  • ~x^2 + y^2 < z^2~ thì tam giác này nhọn.

  • ~x^2 + y^2 = z^2~ thì tam giác này vuông.

  • ~x^2 + y^2 > z^2~ thì tam giác này tù.

Dựa vào các tính chất trên, ta có thể đếm số bộ tam giác tương ứng bằng cách sắp xếp dãy ~a~ lại theo chiều không giảm. Bài toán quy về đếm số bộ ba ~(i,j,k)~ thỏa mãn ~1 \le i < j < k \le n~ và bộ ~(a_i,a_j,a_k)~ tương ứng với ~(x,y,z)~. Ta có thể dùng hai vòng ~for~ để cố định ~i~ và ~j~, sau đó đếm số ~k~ thỏa mãn. Việc này có thể làm bằng tìm kiếm nhị phân hoặc tối ưu nhất là dùng hai con trỏ.

Comments

Please read the guidelines before commenting.


  • -1
    hoangtusaco121  commented on July 9, 2026, 6:39 a.m. ← edit 2

    ...


  • 1
    nhom8cualop6b  commented on Jan. 28, 2026, 1:53 p.m.

    include <bits/stdc++.h>

    using namespace std;

    define Task "CAU5"

    define int long long

    define el '\n'

    define pii pair<int,int>

    define cntbit1 _builtinpopcountll

    define fi first

    define se second

    define pb push_back

    define all(x) x.begin(),x.end()

    define rall(x) x.rbegin(),x.rend()

    define sz(x) (int)x.size()

    define IO freopen(Task".inp","r",stdin); freopen(Task".out","w",stdout);

    define f(i,a,b) for(int i = (a); i <= (b); i++)

    define fr(i,a,b) for(int i = (a); i >= (b); i--)

    define startgame iosbase::syncwithstdio(0); cin.tie(0); cout.tie(0);

    define valorant 0

    const int N= 1e5+7; const int base = 31; const int mod = 1e9+7; const int Inf = 1e18; int n,a[N],b[N],nhon,tu,vuong ; signed main() { startgame IO cin >> n; f(i,1,n){cin >> a[i] ; b[i] = a[i]*a[i];} sort (a+1,a+1+n); sort (b+1,b+1+n); f (i,1,n) { f(j,i+1,n) { int s1 = a[i]+a[j], s2 = b[i]+b[j]; int p1 = lowerbound(a+1+j,a+1+n,s1)-a; int p2 = lowerbound (b+1+j,b+1+n,s2)-b; int p3 = upperbound(b+1+j,b+1+n,s2)-b; nhon += min (p1,p2)-j-1; if (p2!=p3) { if (p1>p2) vuong+=min(p1,p3)-p2; } if (p3<p1) tu+=p1-p3; } } cout << nhon << " "<<vuong << " "<< tu<<el; return valorant; } //☆: .｡. o(≧▽≦)o .｡.:☆ code tham khao xin dung down vote


  • -1
    tranbaphu098  commented on April 24, 2025, 11:37 a.m.

    Ai bt code ko cho tui code vs


  • -7
    hoano1  commented on Jan. 13, 2025, 10:51 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 7
    vuthinh1072008  commented on Aug. 7, 2024, 11:49 a.m.

    Ad ơi tam giác nhọn phải là x ^ 2 + y ^ 2 > z ^ 2 còn tam giác tù là x ^ 2 + y ^ 2 < z ^ 2