Pagini recente » Cod sursa (job #3150389) | Cod sursa (job #179213) | Cod sursa (job #2968166) | Cod sursa (job #297816) | Cod sursa (job #229989)
Cod sursa(job #229989)
#include <stdio.h>
#define DIM 1002
typedef long long tip;
struct punct {
tip x;
tip y;
};
void cre(punct *v, tip n);
void corect(tip poz, punct *v, tip n);
void sort(punct *v, tip n);
punct P[DIM];
punct D[DIM*DIM];
tip n,k,i,j,nr,total;
punct pct(punct a,punct b) {
b.x -= a.x;
b.y -= a.y;
if (b.y<0) {
b.y = -b.y;
b.x = -b.x;
}
return b;
}
tip maiMare(tip a, tip b) {
return D[a].x*D[b].y-D[a].y*D[b].x;
}
int main(){
FILE *f = fopen("trapez.in", "r");
fscanf(f,"%lld",&n);
for (tip i=1;i<=n;i++) {
fscanf(f, "%lld %lld", &P[i].x, &P[i].y);
}
fclose(f);
for (i=1;i<n;i++)
for (j=i+1;j<=n;j++) {
k++;
D[k] = pct(P[i], P[j]);
}
sort(D,k);
k++;
D[k].x = -1;
D[k].y = -1;
nr=1;
for (i=2;i<=k;i++)
if (maiMare(i,i-1)==0)
nr++;
else {
total += (nr*(nr-1)/2);
nr = 1;
}
FILE *g = fopen("trapez.out","w");
fprintf(g,"%lld",total);
fclose(g);
return 0;
}
void cre(punct *v, tip n){
tip i,c,p;
punct aux;
for (i=2;i<=n;i++) {
c = i;
p = i>>1;
while ((p)&&(maiMare(c,p)>0)) {
aux = v[c];
v[c] = v[p];
v[p] = aux;
c = p;
p = p>>1;
}
}
}
void corect(tip poz, punct *v, tip n){
tip p,c;
punct aux;
p = poz;
c = p<<1;
while (c<=n) {
if ((c+1<=n) && (maiMare(c+1,c)>0))
c++;
if (maiMare(c,p)>0) {
aux = v[c];
v[c] = v[p];
v[p] = aux;
p = c;
c = p<<1;
} else break;
}
}
void sort(punct *v, tip n) {
tip i,p,c;
punct aux;
cre(v,n);
for (i=n;i>1;i--) {
aux = v[1];
v[1] = v[i];
v[i] = aux;
corect(1,v,i-1);
}
}