Hướng dẫn giải của HSG THPT Thanh Hóa 2020 - Tam giác
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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ỏ.
Bình luận
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
Ai bt code ko cho tui code vs
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
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