Pagini recente » Cod sursa (job #2533496) | Cod sursa (job #2982803) | Cod sursa (job #1256855) | Cod sursa (job #1429013) | Cod sursa (job #566309)
Cod sursa(job #566309)
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct _nod
{
long int a;
long int b;
struct _nod *adr;
} nod;
typedef struct
{
long int x;
long int y;
} xy;
xy A[1001];
xy B[1000001];
int N;
nod *cap = NULL;
int nr = 0;
int nr1 = 0;
int nr2 = 0;
int acc = 0;
void citire(void)
{
FILE *f = fopen("trapez.in","r");
fscanf(f,"%d ",&N);
for(int i=1;i<=N;i++)
fscanf(f,"%d %d",&A[i].x,&A[i].y);
fclose(f);
}
void add(int a,int b)
{
int Ok = 1;
if(A[a].x == A[b].x)
{
nr1 ++;
Ok = 0;
}
if(A[a].y == A[b].y)
{
nr2 ++;
Ok = 0;
}
if(Ok)
{
B[++acc].x = A[a].y-A[b].y;
B[acc].y = A[a].x-A[b].x;
}
}
void creare(void)
{
for(int i=1;i<=N;i++)
for(int j=i+1;j<=N;j++)
add(i,j);
}
void calc(void)
{
int j;
for(int i=1;i<=acc;i++)
{
j = i+1;
while(j<=acc && B[i].x*B[j].y == B[i].y*B[j].x)
{
nr++;
j ++;
}
}
nr += (nr1*(nr1-1))/2;
nr += (nr2*(nr2-1))/2;
}
long int poz(int li,int ls)
{
xy a = B[(li+ls)/2];
B[(li+ls)/2] = B[1];
B[1] = a;
int c;
int i1 = 0;
int j1 = -1;
int b;
int d;
while(li<ls)
{
if(B[li].y<0)
b = -1;
else
b = 1;
if(B[ls].y<0)
d = -1;
else
d = 1;
if(b*B[li].x*d*B[ls].y>b*B[li].y*d*B[ls].x)
{
a = B[li];
B[li] = B[ls];
B[ls] = a;
c = -i1;
i1 = -j1;
j1 = c;
}
li += i1;
ls += j1;
}
return li;
}
void qsort(int li,int ls)
{
if(li<ls)
{
long int k = poz(li,ls);
qsort(li,k-1);
qsort(k+1,ls);
}
}
int main()
{
FILE *f = fopen("trapez.out","w");
citire();
creare();
qsort(1,acc);
calc();
fprintf(f,"%d",nr);
fclose(f);
return 0;
}