#include #include struct str { int x; int y; int nr; int kto; }*wstr; int n; int wynik[100000]; struct str *wsk_tab[100000], *maly; void wczytanie(void); void minimalny(void); void dnc(int min, int); int comp(const void *a, const void *b); int main() { int i; wczytanie(); minimalny(); dnc(0, 2*n); for(i=1; i<=n; i++) printf("%d\n", wynik[i]); return 0; } /*-----------------------------------------*/ void wczytanie(void) { int i, k; scanf("%d", &n); (wstr)=malloc(2*n*sizeof(struct str)); for(i=0,k=1; i<2*n;i++) { scanf("%d", &(wstr+i)->x); scanf("%d", &(wstr+i)->y); if(inr=i+1; (wstr+i)->kto=1; wsk_tab[i]=(wstr+i); } else { /*duchy*/ (wstr+i)->nr=k; (wstr+i)->kto=0; wsk_tab[i]=(wstr+i); k++; } } } /*-------------------------------------------*/ void minimalny(void) { int i,z=0; for(i=0; i<2*n-1;i++) { if(wsk_tab[i]->y == wsk_tab[z]->y) { if(wsk_tab[i]->x < wsk_tab[z]->x) z=i; } else if(wsk_tab[i]->y < wsk_tab[z]->y) z=i; } wsk_tab[0]=wstr+z; wsk_tab[z]=wstr; } /*-------------------------------------------*/ int comp(const void *a, const void *b) { struct str *A= *(struct str**)a; struct str *B= *(struct str**)b; return((A->x - maly->x)*(B->y -maly->y)-(B->x - maly->x)*(A->y - maly->y)); } /*-------------------------------------------*/ void dnc(int min, int rozmiar) { int i; int pogromcy=0, duchy=0; if(rozmiar==2) { if(wsk_tab[0]->kto==1) { wynik[wsk_tab[0]->nr]=wsk_tab[1]->nr; } else if(wsk_tab[0]->kto==0) { wynik[wsk_tab[1]->nr]=wsk_tab[0]->nr; } } else { maly=wsk_tab[min]; qsort(wsk_tab+1, rozmiar-1, sizeof(struct str *), comp); for(i=0;i<=rozmiar;i++) { if((pogromcy>0) && (pogromcy==duchy)) { if(wsk_tab[0]->kto==1) { wynik[wsk_tab[0]->nr]=wsk_tab[2*duchy-1]->nr; break; } else if(wsk_tab[0]->kto==0) { wynik[wsk_tab[2*duchy-1]->nr]=wsk_tab[0]->nr; break; } } if(wsk_tab[i]->kto==1) pogromcy++; else if (wsk_tab[i]->kto==0) duchy++; } if((i-2)>=2) { dnc(min+1,i-2); } if((rozmiar-i)>=2) { dnc(min+i,rozmiar-i); } } }