Mai intai trebuie sa te autentifici.
Cod sursa(job #1776273)
Utilizator | Data | 11 octombrie 2016 09:03:10 | |
---|---|---|---|
Problema | Numarare triunghiuri | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.88 kb |
#include <bits/stdc++.h>
using namespace std;
int i,j,x,n;
long cnt;
vector<int> V(801);
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
inline bool isTriangle(int a,int b,int c){
if(V[a]+V[b]>=V[c]&&V[b]+V[c]>=V[a]&&V[a]+V[c]>=V[b])
return true;
else
return false;
}
int binSearch(int left, int right){
int best=0;
while(left<right){
int m=(left+right)/2;
if(isTriangle(left,right,best)){
best=m;
left=m+1;
}
else
right=m-1;
}
return best;
}
int main()
{
fin>>n;
vector<int> V(n+1);
V[0]=-1;
for(int i=1;i<=n;i+=1)fin>>V[i];
sort(V.begin(),V.begin()+n+1);
for(i=1;i<n-1;i+=1)
for(j=i+1;j<n;j+=1){
x = binSearch(j+1,n);
if(x!=0)cnt+=x-(j+1)+1;
}
fout<<cnt;
return 0;
}