Pagini recente » Cod sursa (job #350841) | Cod sursa (job #1363293) | Cod sursa (job #1223688) | Cod sursa (job #2477483) | Cod sursa (job #1766357)
#include <stdio.h>
#include <stdlib.h>
int main()
{
FILE *in, *out;
in=fopen("trapez.in", "r");
out=fopen("trapez.out", "w");
int n;
fscanf(in, "%d", &n);
int i,j, k=0, t=0, x[n], y[n];
double p[n*(n-1)/2];// a[n*n], b[n*n];
for(i=0;i<n;i++) fscanf(in, "%d %d", &x[i], &y[i]);
for(i=0;i<n;i++)
for(j=0;j<i;j++){
//a[n*i+j]=x[i]-x[j];
//b[n*i+j]=y[i]-y[j];
p[k]=(x[i]==x[j])?1e10
:2e9*(y[i]-y[j])/(x[i]-x[j]);
k++;
}
//bula(k, p);
squick(p,0,k);
int eg=0;
for(i=0;i<k-1;i++){
while(i<k-1 && p[i]==p[i+1]) {eg++; i++;}
if(eg) {
t=t+eg*(eg+1)/2;
eg=0;
}
}
fprintf(out, "%d", t);
return 0;
}
void sch(double p[], int a, int b){
double m=p[a];
p[a]=p[b];
p[b]=m;
}
void squick(double p[],int jos,int sus){
if(jos+1>=sus) return;
if(jos+2==sus){
if(p[jos]>p[jos+1]) sch(p, jos, jos+1);
return;
}
int piv=(sus+jos)/2;
int i,j=0;
for(i=jos;i<piv-j;i++)
if(p[i]>p[piv]){
j++;
while(piv-j>i && p[piv-j]>p[piv]) j++;
sch(p, i, piv-j);
}
sch(p,piv, piv-j);
piv=piv-j;
j=0;
for(i=sus-1;i>piv+j;i--)
if(p[i]<p[piv]){
j++;
if(i>piv+j) {sch(p, i, piv+j); i++;}
}
sch(p,piv, piv+j);
piv=piv+j;
squick(p,jos,piv);
squick(p,piv+1,sus);
}