#include #include #include #define MAXHASH 262144 #define KOLMY 100000 int zadani,policistu,poruseni; int aktual[MAXHASH]; double zacy[MAXHASH]; double smernice[MAXHASH]; int polvesmeru[MAXHASH]; int kteri[MAXHASH][10]; int kde[MAXHASH]; int polx[512]; int poly[512]; int jestejny(double d1,double d2) { if (d1-d2>1e-8) return 0; if (d2-d1>1e-8) return 0; return 1; } void zahashuj(int m,int n) { int a,b; double y,smer; if (polx[m]==polx[n]) { y=polx[m]; smer=KOLMY; } else { if (polx[m]>polx[n]) { a=m; m=n; n=a; } smer=(double)(poly[n]-poly[m])/(double)(polx[n]-polx[m]); y=poly[m]-smer*polx[m]; } /*printf("(%d,%d),(%d,%d)->%lf,%lf\n",polx[m],poly[m],polx[n],poly[n],y,smer);*/ a=((int)(0.5+(32*y)+(64*smer)))&(MAXHASH-1); for (;aktual[a]==zadani;) { if (jestejny(zacy[a],y)&&jestejny(smernice[a],smer)) break; a=(a+1)&(MAXHASH-1); } if (aktual[a]!=zadani) { aktual[a]=zadani; zacy[a]=y; smernice[a]=smer; polvesmeru[a]=2; kteri[a][0]=m; kteri[a][1]=n; } else { if (polvesmeru[a]==2) { kde[poruseni++]=a; } for (b=0;bpolx[q]) return -1; if (poly[p]poly[q]) return -1; return 0; } int cmpline(const void *p,const void *q) { int m=*((int *)p); int n=*((int *)q); int i; if (m==n) return 0; i=mensi(kteri[m][0],kteri[n][0]); if (i) return -i; i=mensi(kteri[m][1],kteri[n][1]); return -i; } int main() { int i,j,k,l,m,n; for (i=0; i1) qsort((void *)kde,poruseni,sizeof(int),cmpline); if (poruseni) { printf("Tito policiste porusuji smernici:\n"); for (i=0; i