Cod sursa(job #1416704)

Utilizator andrei_r_97Radoi Andrei andrei_r_97 Data 8 aprilie 2015 19:37:43
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <stdio.h>

#define MAX_N 800

#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))

void q_sort(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp, pivot = arr[(i + j) / 2];

  while (i <= j) {
    while (arr[i] < pivot)
      i++;
    while (arr[j] > pivot)
      j--;
    if (i <= j) {
      tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
      i++;
      j--;
    }
  }

  if (i < right)
    q_sort(arr, i, right);
  if (left < j)
    q_sort(arr, left, j);
}

int cautBinMin(int arr[], int start, int len, int val1, int val2) {
  int low = start, hi = len - 1;
  int val = MAX(val1, val2) - MIN(val1, val2);
  int mid;
  while (low <= hi) {
    mid = (low + hi) / 2;
    if (arr[mid] < val) {
      low = mid + 1;
    }
    else {
      hi = mid - 1;
    }
  }

  if (arr[mid] < val)
    mid++;

  return mid;
}

int cautBinMax(int arr[], int start, int len, int val1, int val2) {
  int low = start, hi = len - 1;
  int val = val1 + val2;
  int mid;
  while (low <= hi) {
    mid = (low + hi) / 2;
    if (arr[mid] > val) {
      hi = mid - 1;
    }
    else {
      low = mid + 1;
    }
  }

  if (arr[mid] > val)
    mid--;

  return mid;
}

int main() {

  FILE *in  = fopen("nrtri.in", "r");
  FILE *out = fopen("nrtri.out", "w");

  int n, tri[MAX_N], i, j;
  int ans = 0;
  fscanf(in, "%d", &n);
  for (i = 0; i < n; i++) {
    fscanf(in, "%d", &tri[i]);
  }

  q_sort(tri, 0, n - 1);

  for (i = 0; i < n - 2; i++)
  for (j = i + 1; j < n - 1; j++) {
    int start = cautBinMin(tri, j, n, tri[i], tri[j]);
    int stop  = cautBinMax(tri, j, n, tri[i], tri[j]);
    ans += stop - start + 1;
    if (i >= start && i <= stop)
      ans--;
    if (j >= start && j <= stop)
      ans--;
  }

  fprintf(out, "%d", ans);

  return 0;
}