Pagini recente » Cod sursa (job #1523332) | Cod sursa (job #355673) | Cod sursa (job #989175) | Cod sursa (job #449967) | Cod sursa (job #1208310)
#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;
}