Pagini recente » Cod sursa (job #2630343) | Cod sursa (job #1488523) | Cod sursa (job #1678516) | Cod sursa (job #2357105) | Cod sursa (job #2063627)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n, v[850], nr;
void citire ()
{
int i;
f>>n;
for(i=1;i<=n;++i) f>>v[i];
f.close();
}
void cautabin(int x, int j)
{
int li=j, ls=n ,mid, ok=0;
while (li<=ls)
{
mid=li+(ls-li)/2;
if(v[mid]<=x) {ok=1; break;}
else ls=mid-1;
}
if(ok)
{
int m=mid;
while(v[m]<=x && m>j) m--, nr++;
mid++;
while(v[mid]<=x && mid<=n) mid++, nr++;
}
}
int hoare(int v[], int p, int r)
{
int pivot = v[(p+r)/2];
int i = p - 1, j = r + 1;
while (true)
{
do
{
i++;
} while (v[i] < pivot);
do
{
j--;
} while (v[j] > pivot);
if (i >= j)
return j;
swap(v[i], v[j]);
}
}
void quickSort(int v[], int p, int r)
{
if (p < r)
{
int q = hoare(v, p, r);
quickSort(v, p, q);
quickSort(v, q + 1, r);
}
}
int main()
{
citire();
quickSort(v, 1,n);
int i, j;
for(i=1;i<n;++i)
for(j=i+1;j<=n;++j)
cautabin (v[i]+v[j], j);
g<<nr;
g.close();
}