Cod sursa(job #1208310)

Utilizator hrazvanHarsan Razvan hrazvan Data 15 iulie 2014 13:12:36
Problema Trapez Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <stdio.h>
#define MAXN 1000

int l[MAXN], c[MAXN];
int a[MAXN * MAXN], b[MAXN * MAXN], dr = 0;

void mysort(int st, int dr){
  int i = st, j = dr, piv = (st + dr) / 2, aux;
  while(i <= j){
    while(1LL * a[i] * b[piv] < 1LL * a[piv] * b[i])  i++;
    while(1LL * a[j] * b[piv] > 1LL * a[piv] * b[j])  j--;
    if(i <= j){
      aux = a[i];  a[i] = a[j];  a[j] = aux;
      aux = b[i];  b[i] = b[j];  b[j] = aux;
      i++;  j--;
    }
  }
  if(i < dr)  mysort(i, dr);
  if(st < j)  mysort(st, j);
  return ;
}

int main(){
  FILE *in = fopen("trapez.in", "r");
  int n;
  fscanf(in, "%d", &n);
  int i;
  for(i = 0; i < n; i++){
    fscanf(in, "%d%d", &l[i], &c[i]);
  }
  fclose(in);
  int j;
  for(i = 0; i < n; i++){
    for(j = i + 1; j < n; j++){
      if(c[i] > c[j]){
        a[dr] = l[i] - l[j];
        b[dr] = c[i] - c[j];
      }
      else  if(c[j] > c[i]){
        a[dr] = l[j] - l[i];
        b[dr] = c[j] - c[i];
      }
      else{
        a[dr] = abs(l[i] - l[j]);
        b[dr] = 0;
      }
      dr++;
    }
  }
  mysort(0, dr - 1);
  int lta = a[0], ltb = b[0], ltpoz = 0;
  long long rez = 0;
  for(i = 1; i < dr; i++){
    if(1LL * lta * b[i] < 1LL * ltb * a[i]){
      rez += 1LL * (i - ltpoz) * (i - ltpoz - 1) / 2;
      lta = a[i];  ltb = b[i];  ltpoz = i;
    }
  }
  rez += 1LL * (dr - ltpoz) * (dr - ltpoz - 1) / 2;
  FILE *out = fopen("trapez.out", "w");
  fprintf(out, "%lld", rez);
  fclose(out);
  return 0;
}