Pagini recente » Monitorul de evaluare | Cod sursa (job #2003002) | Cod sursa (job #2020117) | Cod sursa (job #1045822) | Cod sursa (job #807890)
Cod sursa(job #807890)
//
// main.cpp
// Numarare triunghiuri
//
// Created by Ioana Teoc on 11/5/12.
// Copyright (c) 2012 Ioana Teoc. All rights reserved.
//
#include <iostream>
#include<stdio.h>
using namespace std;
#define NMAX 800
int V[NMAX], n;
int partition(int l, int r){
int i = l-1;
int x = V[r];
for(int j = l; j < r; j++){
if(V[j] < x){
i++;
swap(V[i], V[j]);
}
}
swap(V[i+1], V[r]);
return i + 1;
}
void quickSort(int l, int r){
if(l<r){
int q = partition(l, r);
quickSort(l, q-1);
quickSort(q+1, r);
}
}
int binSearch(int x, int l, int r){
int step, i, length = r - l + 1;
for(step = 1; step < length; step <<= 1);
for(i = l - 1; step; step >>= 1){
if(i + step <= r && V[i + step] <= x)
i += step;
}
return i;
}
int searchTri(){
int ntri = 0, q;
for(int i = 0; i < n-2; i++){
for(int j = i+1; j < n-1; j++){
q = binSearch(V[i] + V[j], j+1, n-1);
if(V[i] + V[j] >= V[q])
ntri += q-j;
}
}
return ntri;
}
int main()
{
freopen("nrtri.in", "r", stdin);
freopen("nrtri.out", "w", stdout);
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &V[i]);
}
quickSort(0, n-1);
int res = searchTri();
printf("%d", res);
}